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

Mental Model

Greedy makes the locally optimal choice at each step hoping it leads to global optimum. It works if subproblems have optimal substructure where local best builds to global best.

Analogy: Making change for 8 cents with denominations [1,4,5]. Greedy picks largest first: 5 +1+1+1 (4 coins). But optimal is 4+4 (2 coins) - greedy fails because local choice blocks better future combo.

Amount 8, denoms [5,4,1]:
Greedy: 8 -5→3 -1→2 -1→1 -1→0 (4 coins)
Optimal: 8 -4→4 -4→0 (2 coins)

Dry Run Walkthrough

Input: amount: 8, denoms: [1,4,5]; minimize number of coins using greedy (largest first)

Goal: Show greedy failing to find minimum coins

Step 1: Sort denoms descending: [5,4,1]

remaining=8, denoms=[5,4,1]

Why: Greedy always picks largest possible denom <= remaining

Step 2: Pick 5 (largest <=8), remaining=3

picked=[5], remaining=3

Why: Local best: biggest coin reduces amount most now

Step 3: Next: 4>3, skip; pick 1, remaining=2

picked=[5,1], remaining=2

Why: Continue greedy on remaining

Step 4: Pick 1 (remaining=2→1), then 1 (1→0)

picked=[5,1,1,1], remaining=0

Why: Greedy uses 4 coins

Step 5: Optimal alternative: pick 4 (<=8→4), then 4 (<=4→0)

picked=[4,4], remaining=0

Why: Non-greedy uses 2 coins - greedy fails here

Step 6: Change to amount=30, denoms=[1,5,10,25]

remaining=30, denoms=[25,10,5,1]

Why: Test where greedy works (canonical system)

Step 7: Pick 25 (<=30→5), then 5 (<=5→0)

picked=[25,5], remaining=0

Why: Greedy uses 2 coins, which is optimal

Step 8: No better combo (e.g., 10+10+10=3 coins worse)

Greedy wins here

Why: Local optima align with global in standard coins

Result:

Greedy fails when local choice (big denom) doesn't allow better combos later; works in canonical systems like US coins.

Annotated Code

DSA Typescript

class CoinChanger {
  denoms: number[];

  constructor(denoms: number[]) {
    this.denoms = denoms.sort((a, b) => b - a); // Descending once
  }

  greedyChange(amount: number): { picked: number[], numCoins: number } {
    const picked: number[] = [];
    let remaining = amount;
    for (const denom of this.denoms) {
      while (remaining >= denom) {
        picked.push(denom);
        remaining -= denom;
      }
    }
    return { picked, numCoins: picked.length };
  }
}

// Driver code
function sum(arr: number[]): number { return arr.reduce((a, b) => a + b, 0); }

const failingCase = new CoinChanger([1, 4, 5]);
const greedyFail = failingCase.greedyChange(8);
console.log(`Failing case (amt=8): Greedy picked ${greedyFail.picked.join(', ')} (${greedyFail.numCoins} coins)`);

// Optimal manual: 4+4=2 coins

const workingCase = new CoinChanger([1, 5, 10, 25]);
const greedyWork = workingCase.greedyChange(30);
console.log(`\nWorking case (amt=30): Greedy picked ${greedyWork.picked.join(', ')} (${greedyWork.numCoins} coins) - optimal`);

this.denoms = denoms.sort((a, b) => b - a);

Sort denominations descending once for greedy access to largest first

while (remaining >= denom) { picked.push(denom); remaining -= denom; }

Greedily take as many as possible of current largest denom

Output

Failing case (amt=8): Greedy picked 5, 1, 1, 1 (4 coins)



Working case (amt=30): Greedy picked 25, 5 (2 coins) - optimal

Complexity Analysis

Time: O(d log d + amount / min_denom) where d=denoms.length; sort + greedy picks

Space: O(amount / min_denom) for picked array worst case

vs Alternative: Greedy fast vs DP O(d * amount) which always optimal but slower

Edge Cases

amount = 0

returns empty picked, 0 coins

DSA Typescript

let remaining = amount; // loop skips

no denominations

infinite loop if amount>0, but assume denoms has 1

DSA Typescript

Constructor assumes valid denoms with 1

amount=1, denoms=[1]

picks [1], 1 coin

DSA Typescript

while handles small amounts

When to Use This Pattern

For optimization problems (min/max), try greedy by sorting and picking local best. Prove it works (matroid/canonical) or use DP if future choices matter.

Common Mistakes

Mistake: Using greedy without verifying if local optimum leads to global (e.g., non-canonical coins)
Fix: Test on counterexamples like [1,4,5] for 8; if fails, use DP

Mistake: Not sorting denominations descending
Fix: Always prepare data for greedy: sort largest first

Summary

Greedy succeeds when 'optimal substructure' holds: best choice now + best on remainder = global best.

Fails in cases like non-canonical coin systems where skipping large denom allows better combo.

Key: Prove greedy correct with 'greedy choice property' or fall back to DP.