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

Mental Model

Greedy means making the best choice right now without worrying about the future. It works when these local best choices lead to the best overall solution.

Analogy: Imagine picking coins from a pile to get the most money. If you always pick the biggest coin first, you get the most money quickly. But if some coins are tricky, picking the biggest first might not give the best total.

Coins pile: 25 -> 10 -> 5 -> 1 -> null
Pick biggest coin each time -> total grows fast
But sometimes picking smaller coins first is better

Dry Run Walkthrough

Input: Coins: 25, 10, 5, 1; Amount to make: 30

Goal: Show greedy picks biggest coin first and when it works or fails

Step 1: Pick biggest coin ≤ 30: 25

Picked: 25 -> Remaining amount: 5

Why: Greedy picks biggest coin to reduce amount quickly

Step 2: Pick biggest coin ≤ 5: 5

Picked: 25 -> 5 -> Remaining amount: 0

Why: Greedy finishes with smallest coins to reach exact amount

Step 3: Result: coins picked 25 and 5, total 30

Picked coins: 25 -> 5 -> null

Why: Greedy works here because coins fit amount exactly

Step 4: Change coins to 20, 15, 5, 1; Amount: 30

Coins: 20 -> 15 -> 5 -> 1 -> null

Why: Test when greedy fails

Step 5: Pick biggest coin ≤ 30: 20

Picked: 20 -> Remaining amount: 10

Why: Greedy picks 20 first

Step 6: Pick biggest coin ≤ 10: 5 (twice)

Picked: 20 -> 5 -> 5 -> Remaining amount: 0

Why: Greedy picks 5s since 15 > 10

Step 7: Result: coins picked 20, 5 and 5, total 30

Picked coins: 20 -> 5 -> 5 -> null

Why: Greedy solution uses 3 coins

Step 8: Better solution: pick 15 and 15

Picked coins: 15 -> 15 -> null

Why: Greedy fails because picking two 15s is better but greedy never tries

Result:

Final greedy picks: 20 -> 5 -> 5 -> null (3 coins)
Better picks: 15 -> 15 -> null (2 coins)
Shows greedy can fail if local best choice misses better global solution

Annotated Code

DSA C

#include <stdio.h>

// Function to find minimum coins using greedy
void greedy_coin_change(int coins[], int n, int amount) {
    printf("Coins picked: ");
    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            printf("%d -> ", coins[i]); // pick coin
        }
    }
    printf("null\n");
}

int main() {
    int coins1[] = {25, 10, 5, 1};
    int amount1 = 30;
    printf("Example 1: Coins = 25,10,5,1; Amount = 30\n");
    greedy_coin_change(coins1, 4, amount1);

    int coins2[] = {20, 15, 5, 1};
    int amount2 = 30;
    printf("Example 2: Coins = 20,15,5,1; Amount = 30\n");
    greedy_coin_change(coins2, 4, amount2);

    return 0;
}

while (amount >= coins[i]) {

keep picking current coin while it fits in remaining amount

amount -= coins[i];

reduce amount by picked coin value

printf("%d -> ", coins[i]);

print picked coin to show greedy choice

Output

Example 1: Coins = 25,10,5,1; Amount = 30

Coins picked: 25 -> 5 -> null

Example 2: Coins = 20,15,5,1; Amount = 30

Coins picked: 20 -> 5 -> 5 -> null

Complexity Analysis

Time: O(n) because we check each coin type once and pick as many as possible

Space: O(1) because we only use fixed extra space for counters and output

vs Alternative: Compared to dynamic programming which tries all combinations with O(n*amount) time, greedy is faster but can fail if coins are not standard

Edge Cases

Amount is zero

No coins are picked, output is empty

DSA C

while (amount >= coins[i]) {

Coins do not include 1 and amount cannot be formed exactly

Greedy picks coins until no coin fits, leftover amount remains unhandled

DSA C

while (amount >= coins[i]) {

Single coin type equal to amount

Greedy picks that coin once

DSA C

while (amount >= coins[i]) {

When to Use This Pattern

When a problem asks for making change or selecting items step-by-step with local best choices, check if greedy works by testing if local choices lead to global best.

Common Mistakes

Mistake: Assuming greedy always gives the best solution without checking coin set
Fix: Test greedy on examples and understand coin denominations before trusting greedy

Mistake: Not handling leftover amount when greedy fails to form exact amount
Fix: Add checks or fallback to other methods like dynamic programming

Summary

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

Use greedy when local best choices lead to global best, like standard coin sets.

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