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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following TypeScript code that uses a greedy approach to make change with coins [25, 10, 5, 1] for amount 37?

DSA Typescript

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

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

A [25, 10, 1, 1]

B [25, 5, 5, 1, 1]

C [10, 10, 10, 5, 1, 1]

D [25, 10, 5, 1, 1]

💡 Hint

Think about how the greedy algorithm picks the largest coin first and subtracts it until it can't anymore.

The greedy algorithm picks 25 first (amount left 12), then 10 (amount left 2), then two 1s to make 37. It never picks 5 because 12 < 25 but >= 10, so it picks 10 next.

🧠 Conceptual

intermediate

When Does Greedy Fail for Coin Change?

Given coin denominations [10, 6, 1], which amount below will cause the greedy coin change algorithm to fail to find the minimum number of coins?

A 12

B 15

C 18

D 20

💡 Hint

Try to make 12 with the fewest coins using greedy and compare with the optimal solution.

Greedy picks one 10 coin and two 1 coins (3 coins total) for 12, but the optimal is two 6 coins (2 coins). So greedy fails for 12.

🔧 Debug

advanced

Identify the Bug in Greedy Interval Scheduling

What error does the following TypeScript code produce when trying to select the maximum number of non-overlapping intervals using a greedy approach?

DSA Typescript

interface Interval { start: number; end: number; }

function maxNonOverlapping(intervals: Interval[]): number {
  intervals.sort((a, b) => a.start - b.start);
  let count = 0;
  let lastEnd = -Infinity;
  for (const interval of intervals) {
    if (interval.start >= lastEnd) {
      count++;
      lastEnd = interval.end;
    }
  }
  return count;
}

console.log(maxNonOverlapping([{start:0,end:10},{start:1,end:4},{start:5,end:6}]));

A 2

B TypeError

C 3

D 1

💡 Hint

Check the sorting criteria for intervals in interval scheduling.

The code sorts intervals by start time, but the greedy algorithm for interval scheduling requires sorting by end time. This causes suboptimal selection and count 1 instead of 2.

🚀 Application

advanced

Greedy Algorithm for Activity Selection Output

Given activities with start and end times: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)], what is the output list of selected activities using the greedy algorithm that picks the earliest finishing activity first?

DSA Typescript

interface Activity { start: number; end: number; }

function selectActivities(activities: Activity[]): Activity[] {
  activities.sort((a, b) => a.end - b.end);
  const selected: Activity[] = [];
  let lastEnd = -Infinity;
  for (const activity of activities) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }
  return selected;
}

console.log(selectActivities([{start:1,end:4},{start:3,end:5},{start:0,end:6},{start:5,end:7},{start:8,end:9},{start:5,end:9}]));

A [(1,4), (3,5), (5,7), (8,9)]

B [(1,4), (5,7), (8,9)]

C [(0,6), (5,9)]

D [(3,5), (5,7), (8,9)]

💡 Hint

Sort activities by their end time and pick those that start after the last selected ends.

The greedy algorithm picks (1,4), then (5,7), then (8,9) as they don't overlap and finish earliest.

🧠 Conceptual

expert

Why Greedy Algorithm Fails for 0/1 Knapsack Problem

Why does the greedy algorithm that picks items by highest value-to-weight ratio fail to always find the optimal solution for the 0/1 Knapsack problem?

A Because it does not consider the total weight limit and may pick items that don't fit together optimally

B Because it always picks the smallest items first

C Because it only works when items can be broken into fractions

D Because it sorts items by weight instead of value

💡 Hint

Think about the difference between fractional and 0/1 knapsack problems.

Greedy works for fractional knapsack where items can be split, but fails for 0/1 knapsack because picking by ratio may exclude better combinations.

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