Why Greedy Works and When It Fails in DSA C# - Why This Pattern

Mental Model

Greedy picks the best choice at each step hoping it leads to the best overall result. Sometimes this works perfectly, but sometimes it misses better solutions that need looking ahead.

Analogy: Imagine choosing snacks from a buffet by always picking the tastiest-looking item first without thinking about what comes next. Sometimes you get the best meal, sometimes you miss a better combination.

Choices: [3] -> [2] -> [5] -> [1] -> null
Greedy picks the biggest number at each step.

Dry Run Walkthrough

Input: Set of coins: 1, 3, 4; Goal: make 6 using fewest coins

Goal: Show when greedy picking largest coin first fails to find fewest coins

Step 1: Pick largest coin ≤ 6: 4

Picked: 4 -> Remaining amount: 2

Why: Greedy picks biggest coin first to reduce amount quickly

Step 2: Pick largest coin ≤ 2: 1

Picked: 4 -> 1 -> Remaining amount: 1

Why: Greedy continues picking largest coin possible

Step 3: Pick largest coin ≤ 1: 1

Picked: 4 -> 1 -> 1 -> Remaining amount: 0

Why: Greedy finishes by picking smallest coin repeatedly

Step 4: Check total coins used: 3 coins

Picked coins: 4 -> 1 -> 1

Why: Greedy solution uses 3 coins

Step 5: Compare with better solution: 3 + 3 = 6 with 2 coins

Better solution: 3 -> 3

Why: Greedy fails because it didn't look ahead to pick two 3s

Result:

Greedy picks: 4 -> 1 -> 1 -> null (3 coins)
Better solution: 3 -> 3 -> null (2 coins)

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class CoinChange {
    public static List<int> GreedyCoinChange(int amount, int[] coins) {
        List<int> result = new List<int>();
        Array.Sort(coins);
        Array.Reverse(coins); // Sort descending

        int remaining = amount;
        foreach (int coin in coins) {
            while (coin <= remaining) {
                result.Add(coin); // pick coin
                remaining -= coin; // reduce amount
            }
        }
        return result;
    }

    static void Main() {
        int amount = 6;
        int[] coins = {1, 3, 4};
        List<int> pickedCoins = GreedyCoinChange(amount, coins);
        Console.WriteLine(string.Join(" -> ", pickedCoins) + " -> null");
    }
}

Array.Sort(coins); Array.Reverse(coins);

Sort coins descending to pick largest first

foreach (int coin in coins) { while (coin <= remaining) { result.Add(coin); remaining -= coin; } }

Pick largest coin repeatedly while it fits in remaining amount

Output

4 -> 1 -> 1 -> null

Complexity Analysis

Time: O(n * (amount / min_coin)) because for each coin we may pick it multiple times until amount is reduced

Space: O(amount / min_coin) for storing picked coins in worst case

vs Alternative: Dynamic programming tries all combinations and guarantees minimum coins but costs O(n * amount) time, more expensive but always correct

Edge Cases

Amount is zero

Returns empty list immediately

DSA C#

while (coin <= remaining) { ... } skips if remaining is 0

No coin fits amount

Returns empty list because no coins can be picked

DSA C#

while (coin <= remaining) condition prevents picking

Coins not sorted descending

Greedy may pick smaller coins first, leading to wrong or inefficient solution

DSA C#

Array.Sort(coins); Array.Reverse(coins); ensures descending order

When to Use This Pattern

When a problem asks for an optimal solution by making local best choices step-by-step, check if greedy works by testing if local choices lead to global optimum or if lookahead is needed.

Common Mistakes

Mistake: Assuming greedy always gives the best answer without checking
Fix: Test greedy on small examples and compare with other methods like dynamic programming

Mistake: Not sorting coins descending before greedy selection
Fix: Always sort coins descending to pick largest first

Summary

Greedy picks the best immediate choice hoping for the best overall result.

Use greedy when local best choices lead to global best solution, like in coin sets with special properties.

The key insight is greedy works only if local choices never block better future options.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it sorts the input data before processing

B. Because it tries all possible solutions and picks the best

C. Because it makes the best choice at each step hoping for a global optimum

D. Because it uses recursion to explore all paths

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm picks the best local option at each step without reconsidering previous choices.

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices lead to the overall best solution, which is why greedy works.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option C

4. Quick Check:

   Greedy = best local choice each step [OK]

Hint: Greedy picks best now, hoping for best overall [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with backtracking
• Assuming sorting always means greedy

2. Which of the following is the correct syntax to start a greedy algorithm loop in C# to process a sorted array named arr?

easy

A. foreach (int i in arr.Length)

B. for (int i = 0; i < arr.Length; i++)

C. while (i <= arr.Length)

D. for (int i = 1; i <= arr.Length; i++)

Solution

1. Step 1: Identify correct for loop syntax in C#

   The standard for loop iterates from 0 to less than array length using i < arr.Length.

2. Step 2: Check each option for syntax correctness

   for (int i = 0; i < arr.Length; i++) uses correct syntax; B uses foreach incorrectly; C uses while with undefined i; D uses 1-based index which is off by one.

3. Final Answer:

   for (int i = 0; i < arr.Length; i++) -> Option B

4. Quick Check:

   for loop with i from 0 to length-1 [OK]

Hint: Use for loop from 0 to less than length [OK]

Common Mistakes:

• Using foreach with arr.Length instead of arr
• Starting loop at 1 instead of 0
• Using while without initializing i

3. Consider the following C# code that tries to select the maximum number of non-overlapping intervals using a greedy approach:

var intervals = new List<(int start, int end)> { (1,3), (2,5), (4,7), (6,9) };
intervals.Sort((a,b) => a.end.CompareTo(b.end));
var count = 0;
int lastEnd = int.MinValue;
foreach (var interval in intervals) {
  if (interval.start >= lastEnd) {
    count++;
    lastEnd = interval.end;
  }
}
Console.WriteLine(count);

What is the output of this code?

medium

A. 2

B. 1

C. 4

D. 3

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: (1,3), (2,5), (4,7), (6,9)

2. Step 2: Select intervals greedily

   Pick (1,3) first (count=1, lastEnd=3). Next (2,5) starts before 3, skip. Next (4,7) starts after 3, pick (count=2, lastEnd=7). Next (6,9) starts after 7, pick (count=3, lastEnd=9).

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Greedy interval selection count = 3 [OK]

Hint: Sort by end, pick intervals starting after last end [OK]

Common Mistakes:

• Counting overlapping intervals
• Not sorting by end time
• Updating lastEnd incorrectly

4. The following C# code tries to solve the coin change problem using a greedy approach but sometimes fails. What is the bug?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
Console.WriteLine(count);

medium

A. Greedy fails because coin denominations are not standard, so it misses optimal solution

B. The loop should start from 0, not from coins.Length - 1

C. The while condition should be amount > coins[i], not >=

D. The count variable is not initialized to zero

Solution

1. Step 1: Understand greedy coin change approach

   Greedy picks largest coin first repeatedly until amount is less, then smaller coins.

2. Step 2: Check coin denominations and optimality

   With coins {1,3,4} and amount 6, greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

3. Final Answer:

   Greedy fails because coin denominations are not standard, so it misses optimal solution -> Option A

4. Quick Check:

   Non-standard coins break greedy optimality [OK]

Hint: Greedy fails if coin set is non-standard [OK]

Common Mistakes:

• Thinking loop direction causes failure
• Confusing while condition with off-by-one
• Ignoring coin denomination impact

5. You want to schedule the maximum number of tasks without overlap. Each task has a start and end time. Which approach guarantees the optimal solution and why?

Options:
A) Sort tasks by start time and pick earliest starting tasks
B) Sort tasks by duration and pick shortest tasks first
C) Sort tasks by end time and pick tasks finishing earliest first
D) Pick tasks randomly and check for overlaps

hard

A. Sort tasks by end time and pick tasks finishing earliest first

B. Sort tasks by duration and pick shortest tasks first

C. Sort tasks by start time and pick earliest starting tasks

D. Pick tasks randomly and check for overlaps

Solution

1. Step 1: Understand the interval scheduling problem

   The goal is to select maximum non-overlapping tasks.

2. Step 2: Identify greedy strategy that works

   Sorting by end time and picking earliest finishing tasks ensures maximum room for future tasks, proven optimal.

3. Step 3: Evaluate other options

   Sorting by start time or duration can lead to suboptimal selections; random picks are unreliable.

4. Final Answer:

   Sort tasks by end time and pick tasks finishing earliest first -> Option A

5. Quick Check:

   Earliest finish time greedy = optimal schedule [OK]

Hint: Pick tasks finishing earliest first for max schedule [OK]

Common Mistakes:

• Choosing earliest start time instead of end time
• Picking shortest duration tasks ignoring overlaps
• Assuming random picks can be optimal