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

Mental Model

Greedy algorithm makes the locally optimal choice at each step hoping it leads to a global optimum. It works when the problem has the 'greedy choice property' and optimal substructure.

Analogy: Making change for a dollar: always using the largest coin possible (quarter first) works for US coins, but for weird denominations like 1,3,4 cents for 6 cents, picking 4 then two 1s (3 coins) is worse than two 3s (2 coins).

Target: 6 cents
Coins: [4] [3] [3] [1] [1]
Greedy: pick 4 -> rem 2 -> 1 -> 1 (3 coins)
Optimal: pick 3 -> 3 (2 coins)

Dry Run Walkthrough

Input: coins=[1,5,10,25], target=36 (works); coins=[1,3,4], target=6 (fails)

Goal: Minimum number of coins to make exact target amount using greedy (largest first)

Step 1: Sort coins descending: [25,10,5,1]

target=36

Why: Greedy always picks largest possible coin

Step 2: Pick 25 (<=36), count=1, rem=11

used:25

Why: Largest <= remaining

Step 3: Pick 10 (<=11), count=2, rem=1

used:25,10

Why: Next largest

Step 4: Pick 1 (<=1), count=3, rem=0

used:25,10,1; total coins=3 (optimal!)

Why: Done, greedy works here

Step 5: New: coins=[4,3,1], target=6; sort desc [4,3,1]

target=6

Why: Test failure case

Step 6: Pick 4 (<=6), count=1, rem=2

used:4

Why: Largest first

Step 7: Next largest 3>2, skip; pick 1 (<=2), count=2, rem=1

used:4,1

Why: No 3 fits now

Step 8: Pick 1 (<=1), count=3, rem=0

used:4,1,1; total=3 coins

Why: Greedy finishes

Step 9: Note optimal: two 3s = 2 coins

Greedy=3 > optimal=2

Why: Greedy failed because early large pick blocked better combo

Result:

Greedy works for canonical coin sets (US coins), fails when non-greedy choices lead to fewer coins overall.

Annotated Code

DSA Python

def min_coins_greedy(coins, target):
    coins = sorted(coins, reverse=True)
    count = 0
    i = 0
    while target > 0:
        if i >= len(coins):
            return float('inf')  # can't make
        if coins[i] <= target:
            target -= coins[i]
            count += 1
        else:
            i += 1  # skip too large
    return count

def main():
    # Works
    print('Greedy works:', min_coins_greedy([1,5,10,25], 36))  # 3
    # Fails
    print('Greedy fails:', min_coins_greedy([1,3,4], 6))  # 3 (opt=2)

if __name__ == '__main__':
    main()

coins = sorted(coins, reverse=True)

Sort descending for greedy largest-first

if coins[i] <= target:

Check if current largest fits remaining target

target -= coins[i] count += 1

Use it and increment count

else: i += 1

Skip to next smaller if too big

Output

Greedy works: 3

Greedy fails: 3

Complexity Analysis

Time: O(n log n + target) due to sort + loop over coins/target steps

Space: O(1) extra besides input

vs Alternative: Dynamic Programming solves exactly in O(n * target) time/space, always optimal

Edge Cases

target=0

Returns 0 (no coins needed)

DSA Python

while target > 0:

target=1, coins=[1]

Returns 1

DSA Python

coins[i] <= target

Can't make target (e.g. coins=[3], target=1)

Returns inf

DSA Python

if i >= len(coins): return float('inf')

When to Use This Pattern

Suspect greedy when problem involves optimization (min/max) with choices at each step. Test with examples: if local optimum != global, use DP.

Common Mistakes

Mistake: Using greedy without verifying it works for all cases
Fix: Prove greedy choice property or test counterexamples like non-canonical coins

Mistake: Not handling cases where no coin fits remaining amount
Fix: Add check for impossible and return -1 or inf

Summary

Greedy: pick largest coin <= remaining at each step.

Works when coin denominations are canonical (e.g., powers of base or US coins).

Fails otherwise; use DP for guaranteed optimum.

Key: Does picking local best preclude better global? If yes, greedy fails.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it sorts the input data before processing

B. Because it tries all possible solutions exhaustively

C. Because it uses recursion to explore all paths

D. Because making the best local choice leads to a globally optimal solution

Solution

1. Step 1: Understand greedy algorithm principle

   A greedy algorithm makes the best choice at each step without reconsidering previous choices.

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices add up to the best overall solution.

3. Final Answer:

   Because making the best local choice leads to a globally optimal solution -> Option D

4. Quick Check:

   Greedy = best local choice leads to global optimum [OK]

Hint: Greedy picks best now, works if global best follows [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 pick the next item greedily from a sorted list items in Python?

easy

A. next_item = items.pop(0)

B. next_item = items[0]

C. next_item = items.pop()

D. next_item = items.remove(0)

Solution

1. Step 1: Understand list methods for greedy selection

   To pick and remove the first item, pop(0) removes and returns it.

2. Step 2: Check other options

   items[0] only accesses without removing; pop() removes last; remove(0) removes first occurrence of value 0, not index.

3. Final Answer:

   next_item = items.pop(0) -> Option A

4. Quick Check:

   pop(0) removes first item [OK]

Hint: pop(0) removes and returns first item [OK]

Common Mistakes:

• Using items[0] without removing
• Using pop() removes last item
• Confusing remove() with pop()

3. Consider the following code that tries to select intervals greedily by earliest finish time:

intervals = [(1,4), (2,3), (3,5), (7,8)]
intervals.sort(key=lambda x: x[1])
selected = []
end = 0
for start, finish in intervals:
    if start >= end:
        selected.append((start, finish))
        end = finish
print(selected)

What is the output?

medium

A. [(2, 3), (7, 8)]

B. [(1, 4), (7, 8)]

C. [(2, 3), (3, 5), (7, 8)]

D. [(1, 4), (3, 5), (7, 8)]

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: (2,3), (1,4), (3,5), (7,8)

2. Step 2: Select intervals greedily

   Start with end=0. (2,3) start=2 >=0, select it, end=3. Next (1,4) start=1<3 skip. Next (3,5) start=3>=3 select, end=5. Next (7,8) start=7>=5 select, end=8.

3. Step 3: Final selected intervals

   [(2,3), (3,5), (7,8)]

4. Final Answer:

   [(2, 3), (3, 5), (7, 8)] -> Option C

5. Quick Check:

   Greedy interval selection by finish time = [(2,3),(3,5),(7,8)] [OK]

Hint: Sort by finish time, pick intervals starting after last end [OK]

Common Mistakes:

• Not sorting by finish time
• Selecting overlapping intervals
• Updating end incorrectly

4. The following code tries to solve the coin change problem greedily but has a bug:

coins = [25, 10, 5, 1]
amount = 30
result = []
for coin in coins:
    while amount >= coin:
        result.append(coin)
        amount -= coin
print(result)

What is the bug in this greedy approach?

medium

A. It does not sort coins before using them

B. It fails for some coin sets where greedy is not optimal

C. It uses while instead of if

D. It does not handle zero amount correctly

Solution

1. Step 1: Understand greedy coin change approach

   The code picks largest coin repeatedly until amount is zero.

2. Step 2: Identify when greedy fails

   Greedy works for US coins but fails for some sets (e.g., coins=[10,6,1], amount=12 greedy picks 10+1+1=3 coins but optimal is 6+6=2 coins).

3. Final Answer:

   It fails for some coin sets where greedy is not optimal -> Option B

4. Quick Check:

   Greedy coin change fails on some coin sets [OK]

Hint: Greedy coin change fails if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Thinking sorting is missing
• Confusing while and if usage

5. You want to select the minimum number of intervals to cover a timeline from 0 to 10. Intervals are: [(0,3), (2,6), (5,10), (7,10), (1,4)]. Which greedy strategy will fail to find the minimum set and why? Options: A) Always pick the interval with earliest start time B) Always pick the interval with shortest length C) Always pick the interval with earliest finish time D) Always pick the interval covering the largest uncovered part Choose the failing strategy and explain why.

hard

A. Always picking shortest length fails because it may need many intervals to cover timeline

B. Always picking earliest start fails because it may pick small intervals leaving gaps

C. Always picking earliest finish time works correctly here

D. Always picking largest uncovered part always finds minimum intervals

Solution

1. Step 1: Analyze shortest length strategy

   Picking shortest intervals first may cover small parts, requiring many intervals to cover entire timeline.

2. Step 2: Compare with other strategies

   Earliest finish time is classic greedy that works for interval covering. Largest uncovered part is a complex greedy that can work. Earliest start can fail but less obviously here.

3. Final Answer:

   Always picking shortest length fails because it may need many intervals to cover timeline -> Option A

4. Quick Check:

   Shortest length greedy fails for minimum interval cover [OK]

Hint: Shortest intervals first often leads to many intervals needed [OK]

Common Mistakes:

• Assuming earliest start always works
• Thinking largest uncovered part is always greedy
• Confusing shortest length with earliest finish