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

Concept Flow - Why Greedy Works and When It Fails

Start Problem

↓

Choose Best Local Option

↓

Add to Solution

↓

Is Solution Complete?

No→Repeat Choose Best Local Option

Yes↓

Return Final Solution

↓

Check Optimality

↓

If Works: Greedy is Optimal

↓

If Fails: Greedy is Suboptimal

The greedy method picks the best choice at each step, builds a solution, then checks if it is optimal or fails.

Execution Sample

DSA Typescript

function greedySelect(items) {
  let solution = [];
  let notComplete = true;
  while (notComplete) {
    let choice = bestLocalOption(items);
    solution.push(choice);
    // Update notComplete based on some condition
    notComplete = checkIfComplete(solution, items);
  }
  return solution;
}

This code picks the best local option repeatedly until the solution is complete.

Execution Table

Step	Operation	Choice Made	Solution So Far	Reason Greedy Works/Fails	Visual State
1	Pick best local option	Item A (highest value)	[A]	Works because local best leads to global best	A -> null
2	Pick best local option	Item B (next best)	[A, B]	Works because choices don't conflict	A -> B -> null
3	Pick best local option	Item C	[A, B, C]	Works because problem has greedy-choice property	A -> B -> C -> null
4	Check completeness	All items chosen	[A, B, C]	Solution is optimal	A -> B -> C -> null
5	Example failure	Pick Item X (locally best)	[X]	Fails because local best leads to suboptimal global	X -> null
6	Next pick	Item Y (better globally but not locally)	[X, Y]	Greedy misses better global solution	X -> Y -> null
7	Check completeness	No better local option	[X, Y]	Solution is suboptimal	X -> Y -> null
8	End	Return solution	[X, Y]	Greedy fails here	X -> Y -> null

💡 Execution stops after solution is complete or no better local options exist

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	Final
solution	[]	[A]	[A, B]	[A, B, C]	[X]	[X, Y]	[X, Y]
items	[A,B,C,X,Y]	[B,C,X,Y]	[C,X,Y]	[X,Y]	[Y]	[]	[]
choice	null	A	B	C	X	Y	null

Key Moments - 3 Insights

Why does greedy sometimes fail even if it picks the best local option?

Because the best local option may not lead to the best overall solution if the problem lacks the greedy-choice property, as shown in steps 5-7 where local best choices miss better global solutions.

How do we know greedy works for a problem?

If the problem has the greedy-choice property and optimal substructure, greedy picks at each step lead to a globally optimal solution, as seen in steps 1-4.

What does the 'solution so far' represent in the execution table?

It shows the choices accumulated step-by-step, helping track how the greedy algorithm builds the final solution, visible in the 'Solution So Far' column.

Visual Quiz - 3 Questions

Look at the execution table, what is the solution after step 3?

A [A, B]

B [X, Y]

C [A, B, C]

D [X]

💡 Hint

Check the 'Solution So Far' column at step 3 in the execution table.

At which step does greedy fail to find the optimal solution?

A Step 7

B Step 5

C Step 4

D Step 2

💡 Hint

Look at the 'Reason Greedy Works/Fails' column where it says 'Solution is suboptimal'.

If the problem has the greedy-choice property, how would the solution change in the execution table?

A Greedy picks might miss better options

B Greedy picks always lead to the global best solution

C Solution will be empty

D Solution will have random items

💡 Hint

Refer to steps 1-4 where greedy works because of the greedy-choice property.

Concept Snapshot

Greedy Algorithm:
- Pick best local option at each step
- Add choice to solution
- Repeat until complete
- Works if problem has greedy-choice property
- Fails if local best ≠ global best

Full Transcript

The greedy algorithm solves problems by choosing the best option available at each step without reconsidering previous choices. This works well when the problem has the greedy-choice property, meaning local best choices lead to a globally optimal solution. The execution table shows how the solution builds step-by-step, picking items A, B, and C successfully. However, greedy can fail if the problem lacks this property, as shown when it picks item X first and misses a better global solution involving item Y. Tracking variables like solution and choice helps visualize this process. Understanding when greedy works or fails is key to applying it correctly.

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