Why Greedy Works and When It Fails in DSA Javascript - 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 if Greedy is Optimal

↓

Greedy Works

↓

Greedy Fails: Need Other Methods

Greedy algorithms pick the best choice step-by-step, building a solution. They work when local best choices lead to a global best. Otherwise, they fail.

Execution Sample

DSA Javascript

const coins = [25, 10, 5, 1];
let amount = 30;
let count = 0;
for (const coin of coins) {
  while (amount >= coin) {
    amount -= coin;
    count++;
  }
}
console.log(count);

This code uses a greedy approach to count minimum coins for 30 cents using US coins.

Execution Table

Step	Operation	Amount Left	Coins Used	Action	Visual State
1	Start with amount=30	30	0	Initialize	Amount=30, CoinsUsed=0
2	Use coin 25	30	0	Check if 30 >= 25	Amount=30, CoinsUsed=0
3	Subtract 25	5	1	30 - 25 = 5, count=1	Amount=5, CoinsUsed=1
4	Use coin 25	5	1	Check if 5 >= 25 (No)	Amount=5, CoinsUsed=1
5	Use coin 10	5	1	Check if 5 >= 10 (No)	Amount=5, CoinsUsed=1
6	Use coin 5	5	1	Check if 5 >= 5	Amount=5, CoinsUsed=1
7	Subtract 5	0	2	5 - 5 = 0, count=2	Amount=0, CoinsUsed=2
8	Use coin 5	0	2	Check if 0 >= 5 (No)	Amount=0, CoinsUsed=2
9	Use coin 1	0	2	Check if 0 >= 1 (No)	Amount=0, CoinsUsed=2
10	End	0	2	Amount is 0, done	Amount=0, CoinsUsed=2

💡 Amount reached 0, no more coins needed.

Variable Tracker

Variable	Start	After Step 3	After Step 7	Final
amount	30	5	0	0
count	0	1	2	2
coin	N/A	25	5	1

Key Moments - 3 Insights

Why does the greedy method pick the largest coin first?

Because picking the largest coin reduces the amount fastest, as shown in steps 2 and 3 where 25 is subtracted first, reducing amount from 30 to 5.

When can greedy fail to find the best solution?

Greedy fails when local best choices don't lead to global best. For example, if coins were [10, 7, 1] and amount 14, greedy picks 10 then four 1s (5 coins), but optimal is two 7s (2 coins). This is not shown in the table but is a known limitation.

Why does the loop stop when amount reaches zero?

Because the problem is solved when amount is zero, as shown in step 10 where amount=0 ends the process.

Visual Quiz - 3 Questions

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

A 5

B 25

C 0

D 30

💡 Hint

Check the 'Amount Left' column at step 3 in the execution table.

At which step does the amount become zero?

A Step 10

B Step 3

C Step 7

D Step 9

💡 Hint

Look for the step where 'Amount Left' is 0 in the execution table.

If the coin 25 was removed, how would the coins used change?

A Coins used would decrease

B Coins used would increase

C Coins used would stay the same

D Cannot tell from the table

💡 Hint

Without the largest coin 25, more smaller coins are needed to make 30.

Concept Snapshot

Greedy Algorithm:
- Pick the best local choice at each step
- Build solution step-by-step
- Works if local choices lead to global best
- Fails if local best is not globally optimal
- Example: Coin change with standard coins

Full Transcript

Greedy algorithms solve problems by choosing the best option at each step without reconsidering earlier choices. This works well when the problem has the property that local best choices lead to a global best solution. For example, in the coin change problem with US coins, picking the largest coin first reduces the amount quickly and leads to minimum coins used. The execution table shows how amount decreases from 30 to 0 by subtracting 25, then 5. However, greedy can fail in other coin sets where local best choices do not lead to the minimum number of coins. The process stops when the amount reaches zero. Understanding when greedy works or fails helps choose the right approach for a problem.

Practice

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

easy

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

B. Because it tries all possible solutions before choosing one

C. Because it uses recursion to explore all paths

D. Because it sorts the input data first

Solution

1. Step 1: Understand greedy choice property

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

2. Step 2: Connect greedy choice to global optimum

   This local best choice leads to a global optimum only if the problem has the greedy choice property.

3. Final Answer:

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

4. Quick Check:

   Greedy choice property = best local choice [OK]

Hint: Greedy picks best local choice, not all solutions [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting always solves the problem

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

easy

A. for (const item in arr) {}

B. while (arr.length) {}

C. for (let i = 0; i < arr.length; i++) {}

D. arr.forEach(i => {})

Solution

1. Step 1: Identify standard loop for arrays

   The standard way to loop over array elements by index is for (let i = 0; i < arr.length; i++).

2. Step 2: Check other options

   while (arr.length) loops infinitely unless modified; for...in loops keys, not values; forEach is valid but less common for greedy step control.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) {} -> Option C

4. Quick Check:

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

Hint: Use for loop with index for greedy steps [OK]

Common Mistakes:

• Using for...in for arrays (loops keys)
• Using while without proper exit
• Confusing forEach with for loop syntax

3. What will be the output of the following JavaScript code that tries to select intervals greedily by earliest finish time?

const intervals = [[1,4],[2,3],[3,5]];
intervals.sort((a,b) => a[1] - b[1]);
const result = [];
let lastEnd = 0;
for (const [start, end] of intervals) {
  if (start >= lastEnd) {
    result.push([start, end]);
    lastEnd = end;
  }
}
console.log(result);

medium

A. [[1,4]]

B. [[1,4],[3,5]]

C. [[2,3]]

D. [[2,3],[3,5]]

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [[2,3],[1,4],[3,5]] because 3 < 4 < 5.

2. Step 2: Select intervals greedily

   Start with lastEnd=0. Check [2,3]: 2 >= 0, select it, lastEnd=3. Next [1,4]: 1 < 3, skip. Next [3,5]: 3 >= 3, select it, lastEnd=5.

3. Final Answer:

   [[2,3],[3,5]] -> Option D

4. Quick Check:

   Greedy interval selection = [[2,3],[3,5]] [OK]

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

Common Mistakes:

• Not sorting intervals by finish time
• Selecting overlapping intervals
• Updating lastEnd incorrectly

4. The following code tries to find the minimum number of coins for a given amount using greedy approach with coins [1, 3, 4]. Why does it fail for amount = 6?

const coins = [4, 3, 1];
let amount = 6;
let count = 0;
for (const coin of coins) {
  while (amount >= coin) {
    amount -= coin;
    count++;
  }
}
console.log(count);

medium

A. It outputs 3 but the minimum coins needed is 2

B. It outputs 2 which is correct

C. It causes an infinite loop

D. It outputs 6 which is incorrect

Solution

1. Step 1: Trace greedy coin selection

   Greedy picks 4 once (amount=2), then picks 1 twice (amount=0), total 3 coins.

2. Step 2: Check optimal solution

   Optimal is 2 coins: 3 + 3 = 6, fewer than greedy's 3 coins.

3. Final Answer:

   It outputs 3 but the minimum coins needed is 2 -> Option A

4. Quick Check:

   Greedy fails for coin sets without canonical property [OK]

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

Common Mistakes:

• Assuming greedy always gives minimum coins
• Not checking smaller coin combinations
• Ignoring coin order importance

5. You want to schedule the maximum number of non-overlapping meetings from the list [[0, 30], [5, 10], [15, 20]]. Which approach correctly applies greedy algorithm and what is the maximum number of meetings?

hard

A. Sort by start time, pick earliest start; maximum meetings = 2

B. Sort by finish time, pick earliest finish; maximum meetings = 2

C. Sort by duration, pick shortest; maximum meetings = 3

D. Sort by finish time, pick earliest finish; maximum meetings = 3

Solution

1. Step 1: Sort meetings by finish time

   Sorted: [5,10], [15,20], [0,30] (finish times 10, 20, 30).

2. Step 2: Select meetings greedily

   Pick [5,10], next [15,20] starts after 10, pick it; [0,30] overlaps, skip.

3. Final Answer:

   Sort by finish time, pick earliest finish; maximum meetings = 2 -> Option B

4. Quick Check:

   Greedy by finish time = 2 meetings [OK]

Hint: Sort by finish time for max non-overlapping meetings [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Assuming shortest duration always works
• Counting overlapping meetings