Why Greedy Works and When It Fails in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following JavaScript code that uses a greedy approach to make change for 30 cents with coin denominations [25, 10, 5, 1]?

DSA Javascript

function greedyCoinChange(coins, amount) {
  const result = [];
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}

console.log(greedyCoinChange([25, 10, 5, 1], 30));

A [25, 1, 1, 1, 1, 1]

B [25, 5]

C [5, 5, 5, 5, 5, 5]

D [10, 10, 10]

💡 Hint

Think about how the greedy algorithm picks the largest coin first and subtracts it from the amount repeatedly.

The greedy algorithm picks the largest coin less than or equal to the remaining amount. For 30 cents, it picks 25 first, then 5. So the output is [25, 5].

❓ Predict Output

intermediate

Greedy Algorithm Failure Case Output

What is the output of this greedy coin change code for amount 6 with coin denominations [4, 3, 1]?

DSA Javascript

function greedyCoinChange(coins, amount) {
  const result = [];
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}

console.log(greedyCoinChange([4, 3, 1], 6));

A [4, 1, 1]

B [3, 3]

C [1, 1, 1, 1, 1, 1]

D [4, 3]

💡 Hint

The greedy algorithm picks the largest coin first, but it may not find the minimum number of coins.

The greedy algorithm picks 4 first, then two 1s to make 6. But the optimal solution is two 3s. This shows greedy can fail to find the best solution.

🧠 Conceptual

advanced

Why Greedy Algorithm Works for Activity Selection

Why does the greedy algorithm always find the optimal solution for the Activity Selection problem when activities are sorted by finish time?

A Because it tries all possible combinations to find the best one.

B Because it randomly picks activities and checks if they fit.

C Because it selects the longest activity first to maximize usage.

D Because selecting the earliest finishing activity leaves maximum room for remaining activities.

💡 Hint

Think about how choosing the earliest finishing activity affects the schedule.

Choosing the earliest finishing activity leaves the most time for other activities, ensuring maximum number of non-overlapping activities can be selected.

❓ Predict Output

advanced

Output of Fractional Knapsack Greedy Algorithm

What is the output (total value) of this fractional knapsack greedy algorithm for items with weights [10, 20, 30] and values [60, 100, 120] and knapsack capacity 50?

DSA Javascript

function fractionalKnapsack(weights, values, capacity) {
  const items = weights.map((w, i) => ({weight: w, value: values[i], ratio: values[i] / w}));
  items.sort((a, b) => b.ratio - a.ratio);
  let totalValue = 0;
  let remaining = capacity;
  for (const item of items) {
    if (item.weight <= remaining) {
      totalValue += item.value;
      remaining -= item.weight;
    } else {
      totalValue += item.ratio * remaining;
      break;
    }
  }
  return totalValue;
}

console.log(fractionalKnapsack([10, 20, 30], [60, 100, 120], 50));

A 180

B 220

C 240

D 200

💡 Hint

Sort items by value/weight ratio and fill knapsack greedily, possibly taking fraction of last item.

The items sorted by ratio are: (60/10=6), (100/20=5), (120/30=4). Take all of first two items (weight 30, value 160), then 20 weight from last item (fraction), value 80. Total 240.

🧠 Conceptual

expert

When Does Greedy Algorithm Fail to Find Optimal Solution?

Which of the following scenarios is a known case where a greedy algorithm fails to find the optimal solution?

A Finding minimum number of coins for arbitrary coin denominations.

B Selecting activities sorted by earliest finish time.

C Finding shortest path in a graph with non-negative edges using Dijkstra's algorithm.

D Sorting an array using quicksort.

💡 Hint

Think about coin denominations where greedy picks more coins than needed.

Greedy fails for coin change with arbitrary denominations because it may pick larger coins first and miss the minimal coin count solution.

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