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

Mental Model

Greedy means making the best choice right now without worrying about the future. It works only if these choices lead to the best overall result.

Analogy: Imagine picking coins from a table one by one, always taking the biggest coin you see first. This works if the biggest coins add up to the most money, but fails if smaller coins together are worth more.

Coins on table:
[5] -> [1] -> [10] -> [2] -> null
Greedy picks biggest coin first:
Pick 10 -> Remaining: [5] -> [1] -> [2] -> null

Dry Run Walkthrough

Input: Coins: 5, 1, 10, 2; Greedy picks biggest coin each time

Goal: Show when greedy picking biggest coin works or fails to get max total

Step 1: Pick biggest coin 10 first

Picked: 10
Remaining: 5 -> 1 -> 2 -> null

Why: Greedy picks the biggest coin available now

Step 2: Pick next biggest coin 5

Picked: 10 -> 5
Remaining: 1 -> 2 -> null

Why: Continue picking biggest coin left

Step 3: Pick next biggest coin 2

Picked: 10 -> 5 -> 2
Remaining: 1 -> null

Why: Keep picking biggest coin left

Step 4: Pick last coin 1

Picked: 10 -> 5 -> 2 -> 1
Remaining: null

Why: No coins left

Step 5: Calculate total of picked coins

Total = 10 + 5 + 2 + 1 = 18

Why: Sum of greedy picks

Step 6: Check if picking 5, 2, 1 first is better

Sum = 5 + 2 + 1 = 8, plus 10 later if allowed

Why: Sometimes picking smaller coins first can be better if rules differ

Result:

Picked coins: 10 -> 5 -> 2 -> 1 -> null
Total sum: 18
Greedy works here because picking biggest coin each time leads to max sum.

Annotated Code

DSA Javascript

class CoinPicker {
  constructor(coins) {
    this.coins = coins;
  }

  greedyPick() {
    // Sort coins descending to pick biggest first
    this.coins.sort((a, b) => b - a);
    let picked = [];
    for (let coin of this.coins) {
      picked.push(coin); // pick coin greedily
    }
    return picked;
  }
}

// Driver code
const coins = [5, 1, 10, 2];
const picker = new CoinPicker(coins);
const pickedCoins = picker.greedyPick();
console.log(pickedCoins.join(' -> ') + ' -> null');
const total = pickedCoins.reduce((sum, c) => sum + c, 0);
console.log('Total sum:', total);

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

Sort coins descending to pick biggest first

for (let coin of this.coins) { picked.push(coin); }

Pick coins one by one greedily

Output

10 -> 5 -> 2 -> 1 -> null

Total sum: 18

Complexity Analysis

Time: O(n log n) because sorting the coins takes that time

Space: O(n) because we store the picked coins in a new array

vs Alternative: Alternative is checking all combinations which is O(2^n), greedy is much faster but only works if problem allows

Edge Cases

Empty coin list

Returns empty picked list with sum 0

DSA Javascript

for (let coin of this.coins) { picked.push(coin); }

All coins same value

Greedy picks all coins, sum is total of all coins

DSA Javascript

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

Coins where picking smaller first is better (not handled here)

Greedy fails to find max sum, picks biggest first anyway

DSA Javascript

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

When to Use This Pattern

When a problem asks for making the best immediate choice repeatedly, consider greedy. But check if local best leads to global best, else greedy fails.

Common Mistakes

Mistake: Assuming greedy always gives the best answer
Fix: Verify problem properties like greedy choice property and optimal substructure before using greedy

Summary

Greedy picks the best choice at each step hoping for the best overall result.

Use greedy when local best choices lead to global best solution.

The key is that greedy works only if the problem has the greedy choice property.

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