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

Concept Flow - Why Greedy Works and When It Fails

Start Problem

↓

Choose Best Local Option

↓

Add to Solution

↓

Is Solution Complete?

No→Repeat Choose Best Local Option

Yes↓

Return Final Solution

↓

Check if Greedy is Optimal

↓

If Yes: Greedy Works

↓

If No: Greedy Fails

The greedy approach picks the best local choice repeatedly until the solution is complete, then checks if this leads to the best overall solution.

Execution Sample

DSA Python

items = [(60, 10), (100, 20), (120, 30)]
capacity = 50
items.sort(key=lambda x: x[0]/x[1], reverse=True)
value = 0
for v, w in items:
    if capacity >= w:
        capacity -= w
        value += v

This code sorts items by value/weight ratio and picks items greedily until capacity is full.

Execution Table

Step	Operation	Current Item (Value, Weight)	Capacity Left	Value Accumulated	Action	Visual State
1	Sort items by value/weight ratio	[(60,10),(100,20),(120,30)]	50	0	Sorted as [(60,10),(100,20),(120,30)]	Items sorted by ratio
2	Pick first item	(60,10)	50	0	Capacity >= 10, take item	Capacity=40, Value=60
3	Pick second item	(100,20)	40	60	Capacity >= 20, take item	Capacity=20, Value=160
4	Pick third item	(120,30)	20	160	Capacity < 30, skip item	Capacity=20, Value=160
5	End loop	None	20	160	No more items or capacity full	Final value=160

💡 All items checked or capacity insufficient for next item

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
items	[(60,10),(100,20),(120,30)]	[(60,10),(100,20),(120,30)]	[(60,10),(100,20),(120,30)]	[(60,10),(100,20),(120,30)]	[(60,10),(100,20),(120,30)]	[(60,10),(100,20),(120,30)]
capacity	50	50	40	20	20	20
value	0	0	60	160	160	160

Key Moments - 3 Insights

Why does the greedy approach pick the item with the highest value/weight ratio first?

Because picking the item with the best value per weight locally seems best to maximize total value, as shown in Step 1 and Step 2 of the execution_table.

Why does the greedy approach fail if the next item is too heavy to fit?

Because greedy skips the heavy item even if taking smaller items later might yield better total value, as seen in Step 4 where the third item is skipped due to insufficient capacity.

When does greedy fail to find the optimal solution?

Greedy fails when local best choices do not lead to the global best solution, for example if skipping a heavy item prevents a better combination, as the exit_note and Step 4 illustrate.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value accumulated after picking the second item?

A 160

B 100

C 60

D 180

💡 Hint

Check the 'Value Accumulated' column at Step 3 in the execution_table.

At which step does the greedy algorithm skip an item due to capacity?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column in the execution_table where capacity is less than item weight.

If the capacity was increased to 60, how would the final value change?

A It would remain 160

B It would increase to 280

C It would increase to 220

D It would decrease

💡 Hint

Consider if the third item (120,30) can be taken with capacity 60 after first two items.

Concept Snapshot

Greedy Algorithm:
- Pick best local option at each step
- Add to solution if possible
- Repeat until complete
- Works if local choices lead to global optimum
- Fails if local best misses better global combos

Full Transcript

The greedy algorithm solves problems by choosing the best option available at each step without reconsidering previous choices. It sorts items by a criterion (like value/weight ratio), then picks items while capacity allows. This works well when local best choices lead to the best overall solution. However, it can fail if skipping a heavy item early prevents a better combination later. The example shows picking items by ratio until capacity is full, accumulating value 160. If capacity was larger, more items could be taken for higher value. Understanding when greedy works or fails helps choose the right approach.

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