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.

Practice

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

easy

A. Because it tries all possible solutions and picks the best one

B. Because it uses recursion to explore all paths

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

D. Because it sorts the input data before processing

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 recursion
• Assuming sorting always means greedy

2. Which of the following is the correct syntax to start a greedy algorithm loop in TypeScript to process an array arr?

easy

A. for (let i = 0; i < arr.length; i++) { /* greedy step */ }

B. while (arr.length) { /* greedy step */ }

C. for (const i in arr) { /* greedy step */ }

D. do { /* greedy step */ } while (arr.length)

Solution

1. Step 1: Identify standard for loop syntax

   The standard way to iterate over an array with index in TypeScript is using for (let i = 0; i < arr.length; i++).

2. Step 2: Check other options for correctness

   while (arr.length) { /* greedy step */ } and D use while/do-while but lack index control; for (const i in arr) { /* greedy step */ } uses for...in which iterates keys but is less common and can cause issues.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) { /* greedy step */ } -> Option A

4. Quick Check:

   Standard for loop = for (let i = 0; i < arr.length; i++) { /* greedy step */ } [OK]

Hint: Use for(let i=0; i

Common Mistakes:

• Using for...in for arrays causing unexpected keys
• Missing loop condition causing infinite loops
• Using while without index control

3. Consider the following TypeScript code for selecting intervals greedily by earliest finish time:

const intervals = [[1,4],[3,5],[0,6],[5,7],[8,9],[5,9]];
intervals.sort((a,b) => a[1] - b[1]);
let count = 0;
let end = -Infinity;
for (const [start, finish] of intervals) {
  if (start >= end) {
    count++;
    end = finish;
  }
}
console.log(count);

What is the output?

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [1,4], [3,5], [0,6], [5,7], [8,9], [5,9]

2. Step 2: Select intervals greedily

   Start with end = -Infinity.
   Pick [1,4] (start 1 >= -Infinity), count=1, end=4.
   Next [3,5] start 3 < 4 skip.
   Next [0,6] start 0 < 4 skip.
   Next [5,7] start 5 >= 4 pick, count=2, end=7.
   Next [8,9] start 8 >= 7 pick, count=3, end=9.
   Next [5,9] start 5 < 9 skip.

3. Step 3: Count total selected intervals

   Total count = 3

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Greedy interval count = 3 [OK]

Hint: Sort by finish time, pick non-overlapping intervals [OK]

Common Mistakes:

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

4. The following code attempts to solve the coin change problem greedily by always picking the largest coin first:

const coins = [25, 10, 5, 1];
function greedyChange(amount: number): number {
  let count = 0;
  for (const coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(greedyChange(30));

What is the output and what is the bug if any?

medium

A. 6; Bug: code does not reduce amount correctly

B. 3; Bug: greedy fails for some coin sets

C. Error; Syntax mistake in code

D. 2; No bug, greedy works for US coins

Solution

1. Step 1: Trace greedyChange(30)

   Coins: 25,10,5,1
   25 fits once (30/25=1), count=1, amount=30%25=5
   10 fits zero times (5/10=0), count=1, amount=5
   5 fits once (5/5=1), count=2, amount=0
   1 fits zero times, count=2

2. Step 2: Check if greedy works here

   For US coins, greedy always gives minimum coins. So output is 2 and no bug here.

3. Final Answer:

   2; No bug, greedy works for US coins -> Option D

4. Quick Check:

   Greedy coin change = 2 [OK]

Hint: Greedy coin works for standard US coins [OK]

Common Mistakes:

• Assuming greedy always fails coin change
• Miscomputing amount after division
• Confusing output count with amount

5. You want to select activities from a list with start and end times to maximize the number of activities chosen. However, the activities have a penalty cost if chosen consecutively. Which approach best solves this problem?

hard

A. Use dynamic programming to consider penalties and maximize total benefit

B. Use brute force to try all subsets without pruning

C. Sort activities by start time and pick all that fit ignoring penalties

D. Use a greedy algorithm selecting earliest finishing activities ignoring penalties

Solution

1. Step 1: Understand problem constraints

   Activities have penalties if chosen consecutively, so simple greedy ignoring penalties may fail.

2. Step 2: Choose algorithm considering penalties

   Dynamic programming can track choices and penalties to find maximum benefit, unlike greedy which only looks locally.

3. Final Answer:

   Use dynamic programming to consider penalties and maximize total benefit -> Option A

4. Quick Check:

   Penalties require DP, not greedy [OK]

Hint: Penalties break greedy; use DP for best solution [OK]

Common Mistakes:

• Ignoring penalties and using greedy
• Assuming sorting by start time is enough
• Trying brute force without pruning