Why Greedy Works and When It Fails in DSA Javascript - Quick Recap

Recall & Review

beginner

What is the main idea behind the greedy algorithm approach?

Greedy algorithms make the best choice at each step, hoping to find the overall best solution by building it piece by piece.

intermediate

When does a greedy algorithm guarantee an optimal solution?

When the problem has the greedy-choice property and optimal substructure, meaning local best choices lead to a global best solution.

beginner

Give an example of a problem where greedy algorithms work well.

The activity selection problem, where choosing the earliest finishing activity first leads to the maximum number of activities selected.

intermediate

Why can greedy algorithms fail on some problems?

Because they make decisions based only on immediate benefit without considering future consequences, which can lead to suboptimal overall solutions.

intermediate

Provide an example where greedy algorithms fail to find the best solution.

The coin change problem with coins of 1, 3, and 4 units where greedy picks the largest coin first but does not always produce the minimum number of coins.

What property must a problem have for a greedy algorithm to always work?

A Greedy-choice property

B Randomness

C Backtracking

D Brute force

The greedy-choice property ensures that local optimal choices lead to a global optimal solution.

Which of these problems is a classic example where greedy algorithms succeed?

A Sorting

B Traveling salesman

C Knapsack 0/1

D Activity selection

Activity selection problem can be solved optimally by choosing the earliest finishing activity first.

Why might a greedy algorithm fail on the coin change problem?

A It sorts coins incorrectly

B It ignores future coin combinations

C It uses recursion

D It always picks the smallest coin

Greedy picks the largest coin first without considering if smaller coins combined might use fewer coins overall.

What does 'optimal substructure' mean in greedy algorithms?

A Solution requires backtracking

B Solution is random

C Optimal solution contains optimal solutions to subproblems

D Solution is always brute force

Optimal substructure means the best solution can be built from best solutions of smaller parts.

Which is NOT a characteristic of greedy algorithms?

A Always backtrack to fix mistakes

B Fast and simple

C Build solution step-by-step

D Make locally optimal choices

Greedy algorithms do not backtrack; they commit to choices immediately.

Explain why greedy algorithms work for some problems but fail for others.

Think about how making the best choice now affects the whole solution.

Describe a real-life situation where a greedy approach might fail and why.

Consider choosing something quickly without planning ahead.

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