Why Greedy Works and When It Fails in DSA Typescript - Performance Analysis

Time Complexity: Why Greedy Works and When It Fails

O(n + m)

Understanding Time Complexity

We want to understand how fast greedy algorithms run and why their speed depends on the problem.

When does greedy give a quick solution, and when does it take longer or fail?

Scenario Under Consideration

Analyze the time complexity of this simple greedy approach to the coin change problem.

function greedyCoinChange(coins: number[], amount: number): number {
  let count = 0;
  for (let i = coins.length - 1; i >= 0; i--) {
    while (amount >= coins[i]) {
      amount -= coins[i];
      count++;
    }
  }
  return count;
}
    

This code tries to use the largest coin first repeatedly until the amount is covered or no coins left.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: The inner while loop subtracting coins from amount.
• How many times: Up to amount divided by the smallest coin value.

How Execution Grows With Input

As the amount grows, the number of subtractions grows roughly proportional to amount.

Input Size (amount)	Approx. Operations
10	About 10 subtractions
100	About 100 subtractions
1000	About 1000 subtractions

Pattern observation: The work grows roughly linearly with the amount size.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows with the number of coin types (n) plus the amount (m), because the outer loop is O(n) and total inner iterations are O(m).

Common Mistake

[X] Wrong: "Greedy always finds the best answer quickly for any problem."

[OK] Correct: Greedy works fast but can fail to find the best answer if the problem needs looking ahead or combining choices differently.

Interview Connect

Understanding when greedy works helps you pick the right tool and explain your choices clearly in interviews.

Self-Check

"What if the coin denominations were not sorted or included tricky values? How would that affect the time complexity and correctness?"

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