Classic Failure Cases - When Greedy Fails vs When It Works | OneNoughtOne

0/361

Data Structures & AlgorithmsWhen Greedy Fails vs When It Works

When Greedy Fails vs When It Works

LevelAdvanced

Duration90 mins

TopicWhen Greedy Fails vs When It Works

1 / 4

Classic Failure Cases

The Illusion of Simplicity

Greedy algorithms possess an almost seductive appeal. Their logic is intuitive, their implementation straightforward, and their efficiency often optimal. When a greedy algorithm works, it feels like magic—a complex optimization problem solved by simply making the "obvious" choice at each step.

But here's the uncomfortable truth that every serious algorithm designer must internalize: greedy algorithms fail far more often than they succeed. The very intuition that makes them attractive is also what makes them dangerous. Problems that look amenable to greedy often harbor subtle structures that cause the greedy approach to fail spectacularly.

This page systematically explores the classic failure cases—the problem archetypes where greedy algorithms are guaranteed to produce suboptimal solutions. Understanding these failures is not just about avoiding mistakes; it's about developing the algorithmic intuition to know when to reach for more powerful techniques like dynamic programming or exhaustive search.

Critical Insight

The most insidious greedy failures aren't immediately obvious. A greedy algorithm might produce reasonable solutions most of the time, failing only on specific inputs. This makes testing unreliable as a correctness check—you need theoretical understanding to know when greedy cannot work.

What You Will Learn

By the end of this page, you will be able to identify the structural properties of problems that cause greedy algorithms to fail, understand why the greedy approach breaks down in each classic case, and recognize these patterns when they appear in new, unfamiliar problems.

The Fundamental Reason Greedy Fails

Before cataloging specific failure cases, we must understand the fundamental reason why greedy algorithms fail. At its core, a greedy failure occurs when:

Local optimality does not lead to global optimality.

This happens when the problem has interdependent decisions—when the best choice at one step depends on choices made at later steps. Greedy algorithms, by definition, cannot look ahead. They commit irrevocably to each decision based only on the current state. When future decisions affect the quality of current decisions, greedy approaches are structurally incapable of finding the optimal solution.

Structural Causes of Greedy Failure

•Decision Coupling — The optimal choice at step k depends on what happens at steps k+1, k+2, etc. Greedy cannot see this coupling and makes locally optimal but globally suboptimal choices.
•Overlapping Subproblems — The same subproblem appears multiple times with different contexts. Greedy treats each occurrence independently, missing opportunities for optimization through deduplication.
•Non-Monotonic Payoffs — The value of a choice changes based on what other choices are made. A choice that looks best now may become suboptimal (or vice versa) based on subsequent decisions.
•Constraint Interactions — Multiple constraints interact in complex ways. Satisfying one constraint greedily may make it impossible to satisfy others optimally.
•Delayed Gratification — The optimal solution requires making a short-term sacrifice for long-term gain. Greedy algorithms are constitutionally incapable of delayed gratification.

The Path Dependency Problem:

Consider a greedy algorithm as navigating a decision tree. At each node, greedy chooses the edge that looks locally best. The problem is that this path dependency can lead to dead ends or suboptimal regions of the solution space that greedy cannot escape.

In contrast, dynamic programming considers all paths and caches results, while backtracking can reverse decisions. Greedy has neither capability—once a choice is made, it's permanent, and alternate paths are permanently abandoned.

Mathematical Formulation

Formally, greedy fails when the optimization function f is not separable: f(x₁, x₂, ..., xₙ) ≠ f₁(x₁) + f₂(x₂) + ... + fₙ(xₙ). When decisions interact multiplicatively, through constraints, or through conditional dependencies, the separability assumption breaks.

Classic Failure #1: The 0/1 Knapsack Problem

The 0/1 Knapsack Problem is perhaps the most famous example of greedy failure, particularly illuminating because its closely related cousin—the fractional knapsack—is perfectly suited to greedy.

Problem Statement: Given n items, each with a weight wᵢ and value vᵢ, and a knapsack with capacity W, select a subset of items that maximizes total value while keeping total weight ≤ W. Each item must be taken entirely or not at all (hence "0/1").

Why Greedy Seems Reasonable: The fractional knapsack is solved greedily by taking items in order of value-per-weight ratio. This suggests a natural greedy strategy for 0/1 knapsack: sort by vᵢ/wᵢ and take items in that order until the knapsack is full.

Why Greedy Fails:

Consider this carefully constructed counterexample:

Item	Weight	Value	Value/Weight Ratio
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

Knapsack Capacity: 50

Greedy by Value/Weight Ratio:

Take item A (weight=10, value=60) → capacity remaining: 40
Take item B (weight=20, value=100) → capacity remaining: 20
Item C doesn't fit (weight=30 > 20) → stop

Greedy Solution: {A, B} with total value = 160

Optimal Solution:

Take items B and C: weight = 20 + 30 = 50, value = 100 + 120 = 220

The greedy algorithm achieves only 72.7% of the optimal value!

The Structural Failure

The greedy approach fails because taking item A commits capacity that prevents taking the more valuable combination {B, C}. The decision to take A is locally optimal (highest ratio) but globally suboptimal because it closes off a better path. This is a classic case of decision coupling—the value of taking A depends on what items could have been taken instead.

Deeper Analysis:

The 0/1 knapsack failure illustrates a profound principle: discrete choices create interdependencies that continuous choices do not.

In fractional knapsack, we can take 0.5 of item A and 0.5 of item B. This continuity means we never face "all or nothing" decisions that foreclose future options. The solution space is convex, and local optima are global optima.

In 0/1 knapsack, the solution space is discrete—a collection of isolated points (subsets). Moving from one point to another requires removing and adding entire items. This discreteness creates non-convexity, where local optima can be far from global optima.

Mathematical Consequence: The 0/1 knapsack is NP-hard, meaning (assuming P ≠ NP) no polynomial-time algorithm can solve it optimally for all inputs. Greedy provides a polynomial-time algorithm, but at the cost of suboptimality. The correct approach is dynamic programming with O(nW) time complexity (pseudo-polynomial).

knapsack_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def greedy_knapsack_01(items, capacity):
    """
    Greedy 0/1 Knapsack - sorts by value/weight ratio.
    WARNING: This does NOT give optimal solutions!
    """
    # Sort by value-to-weight ratio (descending)
    sorted_items = sorted(items, key=lambda x: x['value'] / x['weight'], reverse=True)
    
    total_value = 0
    total_weight = 0
    selected = []
    
    for item in sorted_items:
        if total_weight + item['weight'] <= capacity:
            selected.append(item['name'])
            total_value += item['value']
            total_weight += item['weight']
    
    return total_value, selected
 
def dp_knapsack_01(items, capacity):
    """
    Dynamic Programming 0/1 Knapsack - guaranteed optimal.
    Time: O(n * capacity), Space: O(n * capacity)
    """
    n = len(items)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Take item i-1 if it fits
            if items[i-1]['weight'] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - items[i-1]['weight']] + items[i-1]['value'])
    
    # Reconstruct solution
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(items[i-1]['name'])
            w -= items[i-1]['weight']
    
    return dp[n][capacity], selected[::-1]
 
# Counterexample demonstrating greedy failure
items = [
    {'name': 'A', 'weight': 10, 'value': 60},
    {'name': 'B', 'weight': 20, 'value': 100},
    {'name': 'C', 'weight': 30, 'value': 120},
]
capacity = 50
 
greedy_value, greedy_selection = greedy_knapsack_01(items, capacity)
optimal_value, optimal_selection = dp_knapsack_01(items, capacity)
 
print(f"Greedy: value={greedy_value}, items={greedy_selection}")
print(f"Optimal: value={optimal_value}, items={optimal_selection}")
print(f"Greedy achieves {greedy_value/optimal_value*100:.1f}% of optimal")

Classic Failure #2: The Coin Change Problem

The Coin Change Problem is particularly instructive because the greedy approach works for some coin systems (like US currency) but fails for others—demonstrating that the correctness of greedy can depend on the specific input structure, not just the problem type.

Problem Statement: Given a set of coin denominations {d₁, d₂, ..., dₖ} and a target amount n, find the minimum number of coins needed to make exactly n cents.

The Greedy Approach: Repeatedly take the largest coin that doesn't exceed the remaining amount. This is what cashiers do instinctively, and it works perfectly for US currency {1, 5, 10, 25}.

Why Greedy Works for US Currency:

For US coins {1, 5, 10, 25}, the greedy algorithm is optimal. This is because the denominations have a special property: each denomination is an integer multiple of smaller ones in a way that prevents greedy from making irreversible mistakes. Specifically:

25 = 5 × 5 (not 2 × 10 + 5)
10 = 2 × 5
5 = 5 × 1

This structure—called a canonical coin system or greedy-compatible system—ensures that using larger coins first never blocks the optimal solution.

When Greedy Fails:

Consider the non-canonical coin system: {1, 3, 4} with target amount 6.

Greedy Approach

•Target: 6, Coins: {1, 3, 4}
•Take largest coin ≤ 6: coin 4 → remaining: 2
•Take largest coin ≤ 2: coin 1 → remaining: 1
•Take largest coin ≤ 1: coin 1 → remaining: 0
•Greedy uses 3 coins: {4, 1, 1}

Optimal Solution

•Target: 6, Coins: {1, 3, 4}
•Instead of starting with 4...
•Use two 3-cent coins
•3 + 3 = 6 exactly
•Optimal uses 2 coins: {3, 3}

The Structural Failure

Greedy picks the 4-cent coin because it's the largest that fits. But this choice forecloses the optimal path. Once we take 4, we need 2 more—but 2 cannot be made efficiently with {1, 3, 4}. The "locally worse" choice of starting with 3 enables a globally better outcome.

More Counterexamples:

Coin System	Target	Greedy Solution	Optimal Solution	Greedy Coins	Optimal Coins
{1, 3, 4}	6	4+1+1	3+3	3	2
{1, 5, 7}	10	7+1+1+1	5+5	4	2
{1, 6, 9}	12	9+1+1+1	6+6	4	2
{1, 3, 9, 10}	28	10+10+3+3+1+1	10+9+9	6	3

Pattern Recognition: Greedy fails when there exist denominations that combine more efficiently than using the largest coin first. This typically happens when denominations are not sufficiently "spread out" or when multiple mid-range coins can combine to match or exceed a larger coin's utility.

The Mathematical Criterion:

A coin system is greedy-compatible (canonical) if and only if, for all amounts n:

Greedy(n) = Optimal(n)

Determining whether a coin system is greedy-compatible is itself a non-trivial problem. For US currency, it can be verified. For arbitrary coin systems, the problem requires analysis.

Key Theorem (Kozen & Zaks, 1994): For a coin system to be greedy-compatible, the greedy solution for every amount from 1 to the largest denomination plus the second-largest denomination must be optimal. This provides a finite (but potentially large) verification procedure.

General Solution - Dynamic Programming: For arbitrary coin systems, the minimum coin change problem requires dynamic programming:

dp[i] = min(dp[i - c] + 1) for all coins c ≤ i

Base case: dp[0] = 0

Time complexity: O(n × k) where k is the number of denominations.

coin_change_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def greedy_coin_change(coins, amount):
    """
    Greedy coin change - works only for canonical coin systems!
    Returns (num_coins, coin_list) or (inf, []) if impossible.
    """
    coins = sorted(coins, reverse=True)  # Sort descending
    result = []
    remaining = amount
    
    for coin in coins:
        while remaining >= coin:
            result.append(coin)
            remaining -= coin
    
    if remaining == 0:
        return len(result), result
    return float('inf'), []
 
def dp_coin_change(coins, amount):
    """
    Dynamic programming coin change - always optimal.
    Time: O(amount * len(coins))
    """
    # dp[i] = (min coins to make amount i, list of coins used)
    dp = [(float('inf'), []) for _ in range(amount + 1)]
    dp[0] = (0, [])
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin][0] + 1 < dp[i][0]:
                dp[i] = (dp[i - coin][0] + 1, dp[i - coin][1] + [coin])
    
    return dp[amount]
 
# Test cases demonstrating greedy failures
test_cases = [
    ({'coins': [1, 3, 4], 'amount': 6}),
    ({'coins': [1, 5, 7], 'amount': 10}),
    ({'coins': [1, 6, 9], 'amount': 12}),
    ({'coins': [1, 3, 9, 10], 'amount': 28}),
]
 
print("Demonstrating Greedy Failures in Coin Change:
")
for tc in test_cases:
    coins, amount = tc['coins'], tc['amount']
    greedy_num, greedy_coins = greedy_coin_change(coins, amount)
    optimal_num, optimal_coins = dp_coin_change(coins, amount)
    
    print(f"Coins: {coins}, Amount: {amount}")
    print(f"  Greedy:  {greedy_num} coins -> {greedy_coins}")
    print(f"  Optimal: {optimal_num} coins -> {optimal_coins}")
    status = "✓ Same" if greedy_num == optimal_num else f"✗ Greedy uses {greedy_num - optimal_num} extra coins"
    print(f"  Result:  {status}
")

Classic Failure #3: Shortest Paths with Negative Edge Weights

Dijkstra's algorithm is one of the most celebrated greedy algorithms—elegant, efficient, and exactly optimal for single-source shortest paths. But it has a critical limitation that exemplifies a fundamental greedy failure mode: it fails with negative edge weights.

Why Dijkstra Fails:

Dijkstra's greedy choice is: "The unvisited vertex with the smallest current distance IS the shortest path to that vertex."

This relies on a critical assumption: relaxing edges can only decrease distances, and once we've found the shortest path to a vertex, no later path can improve it.

With negative edges, this assumption breaks. An edge with weight -5 can decrease the distance to a vertex we've already finalized. The greedy choice—committing to the closest unvisited vertex—becomes premature.

Concrete Counterexample:

Consider this graph with vertices A, B, C and edges:

A → B: weight 1
A → C: weight 5
B → C: weight -10

We want the shortest path from A to C.

Dijkstra's Execution:

Initialize: dist[A] = 0, dist[B] = ∞, dist[C] = ∞
Process A (smallest distance): Update dist[B] = 1, dist[C] = 5
Process B (dist=1 < dist[C]=5): Update dist[C] = 1 + (-10) = -9
Process C: Nothing to update

Result: dist[C] = -9 ✓ (Happens to be correct!)

But the issue is order dependency. If we slightly modify the algorithm's tie-breaking or structure, or use certain implementations, the result can be wrong.

A Clearer Failure Case:

Consider this graph:

A → B: weight 2
A → C: weight 4
B → D: weight 1
C → D: weight -5
C → B: weight -3

Shortest path from A to D:

Dijkstra's Execution:

dist[A]=0. Process A: dist[B]=2, dist[C]=4
dist[B]=2 is minimum. Process B: dist[D]=3. Mark B as finalized.
dist[D]=3 is minimum. Process D. Mark D as finalized with dist=3.
dist[C]=4 is minimum. Process C:
- C → D would give 4 + (-5) = -1, but D is already finalized!
- C → B would give 4 + (-3) = 1, but B is already finalized!

Dijkstra returns dist[D] = 3

Actual Shortest Path: A → C → D with weight 4 + (-5) = -1, or A → C → B → D with weight 4 + (-3) + 1 = 2

Both are shorter than 3!

The Core Issue

Dijkstra's greedy commitment is: "Once a vertex is finalized, its distance is optimal and will never change." Negative edges violate this invariant. A longer initial path might later become shorter via negative-weight edges—but greedy has already committed and won't revisit.

Correct Algorithms for Negative Edges:

1. Bellman-Ford Algorithm

Relaxes ALL edges V-1 times
No greedy commitment—every edge is reconsidered multiple times
Time complexity: O(V × E)
Can also detect negative cycles

2. SPFA (Shortest Path Faster Algorithm)

Queue-based variant of Bellman-Ford
Only re-relaxes vertices whose distances have changed
Empirically faster on many graphs, but worst-case is still O(V × E)

Key Insight: The non-greedy approach works because it doesn't finalize any vertex until ALL relaxations are complete. It trades efficiency for correctness—Bellman-Ford is O(VE) vs Dijkstra's O((V+E)log V).

Shortest Path Algorithm Comparison
Algorithm	Greedy?	Negative Edges?	Negative Cycles?	Time Complexity
Dijkstra	Yes	No ✗	No	O((V+E) log V)
Bellman-Ford	No	Yes ✓	Detects	O(V × E)
Floyd-Warshall	No (DP)	Yes ✓	Detects	O(V³)
Johnson's	Mixed	Yes ✓	No (fails)	O(V² log V + VE)

Classic Failure #4: Weighted Independent Set

The Weighted Independent Set Problem is another canonical example where greedy intuition leads astray. This problem appears in many guises: scheduling jobs on a single machine, allocating resources without conflicts, and selecting compatible activities.

Problem Statement: Given a graph G = (V, E) where each vertex v has a weight w(v), find a subset S ⊆ V such that:

S is an independent set (no two vertices in S are adjacent)
The total weight Σw(v) for v ∈ S is maximized

Greedy Strategy: A natural greedy approach: repeatedly select the highest-weight vertex that doesn't conflict with already-selected vertices.

Counterexample:

Consider a path graph with 4 vertices:

A(weight=10) — B(weight=20) — C(weight=20) — D(weight=10)

Edges connect adjacent vertices: A-B, B-C, C-D.

Greedy by Maximum Weight:

Select B (weight=20, highest)
A and C are now blocked (adjacent to B)
Select D (weight=10, only remaining non-blocked vertex)

Greedy Solution: {B, D} with total weight = 30

Optimal Solution:

Select A and C: they are not adjacent (B separates them)
{A, C} with total weight = 10 + 20 = 30

Wait, same weight! Let's try a different example:

A(weight=5) — B(weight=100) — C(weight=100) — D(weight=5)

Greedy:

Select B (weight=100)
A and C blocked
Select D (weight=5)

Greedy: {B, D} = 105

Optimal:

{B} alone = 100 (not better)
{A, C} = 5 + 100 = 105 (same)

Let's be more precise:

A(weight=1) — B(weight=1000) — C(weight=1000) — D(weight=1)

Greedy:

Select B (weight=1000)
A and C blocked
Select D (weight=1)

Greedy: {B, D} = 1001

But we could select {A, C} = 1 + 1000 = 1001 — still the same!

The issue is that for path graphs, dynamic programming gives optimal solutions efficiently, and greedy happens to work reasonably well. Let's try a star graph instead.

Star Graph Counterexample:

Consider a star graph with center vertex X connected to leaves L₁, L₂, L₃, L₄, L₅:

        L₁(weight=10)
        |
        X(weight=15) — L₂(weight=10)
       /|
      L₃ L₄ L₅
   (weight=10 each)

All leaves have weight 10, center has weight 15.

Greedy by Maximum Weight:

Select X (weight=15, highest)
All leaves L₁, L₂, L₃, L₄, L₅ are now blocked (adjacent to X)

Greedy: {X} = 15

Optimal:

Select all leaves: {L₁, L₂, L₃, L₄, L₅}
No two leaves are adjacent (they only connect to X)
Total weight = 10 × 5 = 50

Greedy achieves only 30% of optimal!

The Structural Failure

Selecting the highest-weight vertex blocks all its neighbors. If a vertex has many high-weight neighbors, it may be better to skip that vertex despite its high weight. Greedy cannot evaluate this tradeoff—it only sees local weights, not global connectivity patterns.

General Graph Complexity:

The Weighted Independent Set problem on general graphs is NP-hard. There is no known polynomial-time algorithm, and greedy provides no approximation guarantee.

Special Cases:

Tree graphs: DP gives O(n) optimal solution
Bipartite graphs: Still NP-hard
Interval graphs: Greedy DOES work (this is the activity selection problem!)
Chordal graphs: DP/greedy combinations work

Key Insight: The graph structure determines whether greedy can work. The same problem—select maximum weight non-conflicting items—is solved greedily for intervals but requires DP or exhaustive search for general graphs. Recognizing graph structure is crucial for algorithm selection.

Classic Failure #5: The Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is the poster child for NP-hard optimization problems. Various greedy heuristics exist, and while they can produce adequate solutions for practical purposes, they fundamentally cannot guarantee optimality.

Problem Statement: Given n cities and distances d(i,j) between each pair, find the shortest tour that visits every city exactly once and returns to the starting city.

Greedy Heuristics:

Nearest Neighbor: From the current city, go to the closest unvisited city.
Nearest Insertion: Build a tour by repeatedly inserting the city that causes minimum increase.
Greedy Edge: Add edges in order of increasing length, skipping edges that would create a cycle (before all cities are visited) or degree > 2.

Nearest Neighbor Counterexample:

Consider 4 cities with distances:

	A	B	C	D
A	0	1	10	10
B	1	0	10	2
C	10	10	0	1
D	10	2	1	0

Nearest Neighbor from A:

A → B (distance 1, closest)
B → D (distance 2, closest unvisited)
D → C (distance 1, only option)
C → A (distance 10, return)

Greedy Tour: A → B → D → C → A = 1 + 2 + 1 + 10 = 14

Better Tour: A → B → D → C isn't optimal! Consider: A → C → D → B → A = 10 + 1 + 2 + 1 = 14 (same, different path) A → B → C → D → A = 1 + 10 + 1 + 10 = 22 (worse) A → C → B → D → A = 10 + 10 + 2 + 10 = 32 (worse)

Actually, for this specific example, greedy ties with optimal. Let's construct a worse case.

Classic TSP Greedy Failure:

Consider 5 cities arranged adversarially:

    B
   /|
  1 | 1
 /  |  
A---+---C
 \  |  /
  1 | 1
   \|/
    D
    |
   100
    |
    E

Distances:

A-B: 1, A-C: 2, A-D: 1
B-C: 1, B-D: 100
C-D: 1
D-E: 100
Others: all 100

Nearest Neighbor from A:

A → B (1) or A → D (1) — say A → B
B → C (1)
C → D (1)
D → E (100) — only unvisited
E → A (100) — return

Greedy: 1 + 1 + 1 + 100 + 100 = 203

Optimal Tour: A → D → E → C → B → A But wait, we need all distances...

The key insight is that nearest neighbor can get "trapped" by short local edges and forced into long edges at the end. A more careful tour ordering can avoid the long edges.

Competitive Ratio: The nearest neighbor heuristic can be a factor of O(log n) worse than optimal. No greedy heuristic for TSP has a constant approximation ratio unless P = NP.

The Fundamental Limitation

TSP exhibits extreme decision coupling. The very first edge chosen influences all subsequent possibilities and especially the final "closing" edge. Greedy algorithms choosing short edges early can force arbitrarily long edges later. The optimal tour requires global coordination that no local strategy can achieve.

TSP Solution Approaches
Method	Type	Guarantee	Complexity
Brute Force	Exact	Optimal	O(n!)
Dynamic Programming	Exact	Optimal	O(n² × 2ⁿ)
Branch & Bound	Exact	Optimal	Exponential (pruned)
Nearest Neighbor	Greedy	O(log n) approx	O(n²)
Christofides	Approximation	1.5× approx	O(n³)
Lin-Kernighan	Local Search	Empirically good	Variable

Pattern Recognition: When to Suspect Greedy Will Fail

After examining these classic failures, clear patterns emerge. Here is a checklist for recognizing when greedy is likely to fail:

Warning Signs That Greedy Will Fail

•Discrete all-or-nothing choices — When items must be taken entirely or not at all (0/1 decisions), greedy commitments foreclose combinations that might be superior.
•Non-canonical number systems — When denomination/value structures don't align hierarchically, smaller components can combine more efficiently than larger ones taken greedily.
•Negative values or decreasing costs — When costs can decrease as you proceed, early commitments become premature. Greedy can't anticipate future discounts.
•High vertex degrees / many conflicts — In graph problems, high-degree vertices block many options. Taking them greedily might exclude collectively superior alternatives.
•Closed cycles or return constraints — When solutions must form cycles (like TSP), early choices affect end-game options in ways greedy cannot foresee.
•Overlapping subproblems — When the same subproblem appears with different contexts, greedy's lack of memory causes redundant or inconsistent decisions.
•Multi-objective optimization — When multiple criteria must be balanced, greedy optimization of one criterion can sabotage others.
•The problem is NP-hard — Most NP-hard optimization problems cannot be solved optimally by greedy (though greedy heuristics may yield acceptable approximations).

The Litmus Test

Ask yourself: "Can making the locally best choice ever block a globally better path?" If the answer is yes—or even maybe—greedy is suspect. Try to construct a counterexample. If you can find one, greedy fails. If you cannot after earnest effort, investigate whether a proof of correctness exists.

Summary: Classic Greedy Failure Cases

We have examined the most instructive cases where greedy algorithms fail to produce optimal solutions. Each failure illuminates a fundamental limitation of the greedy paradigm:

Summary of Classic Greedy Failures
Problem	Why Greedy Fails	Correct Approach
0/1 Knapsack	Discrete choices foreclose optimal combinations	Dynamic Programming O(nW)
Coin Change (non-canonical)	Smaller coins combine more efficiently	Dynamic Programming O(nk)
Shortest Paths (negative edges)	Early finalization misses later improvements	Bellman-Ford O(VE)
Weighted Independent Set	High-degree vertices block superior alternatives	DP on trees; NP-hard generally
Traveling Salesman	Early edges force bad closing edges	DP O(n²2ⁿ); approximations

Page Complete

You now understand the classic cases where greedy algorithms fail. The next page will teach you how to systematically construct counterexamples to demonstrate when a specific greedy approach is incorrect—a critical skill for both algorithm design and technical interviews.

Data Structures & AlgorithmsWhen Greedy Fails vs When It Works

When Greedy Fails vs When It Works

LevelAdvanced

Duration90 mins

TopicWhen Greedy Fails vs When It Works

1 / 4

Classic Failure Cases

The Illusion of Simplicity

Critical Insight

What You Will Learn

The Fundamental Reason Greedy Fails

Before cataloging specific failure cases, we must understand the fundamental reason why greedy algorithms fail. At its core, a greedy failure occurs when:

Local optimality does not lead to global optimality.

Structural Causes of Greedy Failure

•Decision Coupling — The optimal choice at step k depends on what happens at steps k+1, k+2, etc. Greedy cannot see this coupling and makes locally optimal but globally suboptimal choices.
•Overlapping Subproblems — The same subproblem appears multiple times with different contexts. Greedy treats each occurrence independently, missing opportunities for optimization through deduplication.
•Non-Monotonic Payoffs — The value of a choice changes based on what other choices are made. A choice that looks best now may become suboptimal (or vice versa) based on subsequent decisions.
•Constraint Interactions — Multiple constraints interact in complex ways. Satisfying one constraint greedily may make it impossible to satisfy others optimally.
•Delayed Gratification — The optimal solution requires making a short-term sacrifice for long-term gain. Greedy algorithms are constitutionally incapable of delayed gratification.

The Path Dependency Problem:

Mathematical Formulation

Classic Failure #1: The 0/1 Knapsack Problem

Why Greedy Fails:

Consider this carefully constructed counterexample:

Item	Weight	Value	Value/Weight Ratio
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

Knapsack Capacity: 50

Greedy by Value/Weight Ratio:

Take item A (weight=10, value=60) → capacity remaining: 40
Take item B (weight=20, value=100) → capacity remaining: 20
Item C doesn't fit (weight=30 > 20) → stop

Greedy Solution: {A, B} with total value = 160

Optimal Solution:

Take items B and C: weight = 20 + 30 = 50, value = 100 + 120 = 220

The greedy algorithm achieves only 72.7% of the optimal value!

The Structural Failure

Deeper Analysis:

The 0/1 knapsack failure illustrates a profound principle: discrete choices create interdependencies that continuous choices do not.

knapsack_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def greedy_knapsack_01(items, capacity):
    """
    Greedy 0/1 Knapsack - sorts by value/weight ratio.
    WARNING: This does NOT give optimal solutions!
    """
    # Sort by value-to-weight ratio (descending)
    sorted_items = sorted(items, key=lambda x: x['value'] / x['weight'], reverse=True)
    
    total_value = 0
    total_weight = 0
    selected = []
    
    for item in sorted_items:
        if total_weight + item['weight'] <= capacity:
            selected.append(item['name'])
            total_value += item['value']
            total_weight += item['weight']
    
    return total_value, selected
 
def dp_knapsack_01(items, capacity):
    """
    Dynamic Programming 0/1 Knapsack - guaranteed optimal.
    Time: O(n * capacity), Space: O(n * capacity)
    """
    n = len(items)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Take item i-1 if it fits
            if items[i-1]['weight'] <= w:
                dp[i][w] = max(dp[i][w], 
                              dp[i-1][w - items[i-1]['weight']] + items[i-1]['value'])
    
    # Reconstruct solution
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(items[i-1]['name'])
            w -= items[i-1]['weight']
    
    return dp[n][capacity], selected[::-1]
 
# Counterexample demonstrating greedy failure
items = [
    {'name': 'A', 'weight': 10, 'value': 60},
    {'name': 'B', 'weight': 20, 'value': 100},
    {'name': 'C', 'weight': 30, 'value': 120},
]
capacity = 50
 
greedy_value, greedy_selection = greedy_knapsack_01(items, capacity)
optimal_value, optimal_selection = dp_knapsack_01(items, capacity)
 
print(f"Greedy: value={greedy_value}, items={greedy_selection}")
print(f"Optimal: value={optimal_value}, items={optimal_selection}")
print(f"Greedy achieves {greedy_value/optimal_value*100:.1f}% of optimal")

Classic Failure #2: The Coin Change Problem

Problem Statement: Given a set of coin denominations {d₁, d₂, ..., dₖ} and a target amount n, find the minimum number of coins needed to make exactly n cents.

The Greedy Approach: Repeatedly take the largest coin that doesn't exceed the remaining amount. This is what cashiers do instinctively, and it works perfectly for US currency {1, 5, 10, 25}.

Why Greedy Works for US Currency:

25 = 5 × 5 (not 2 × 10 + 5)
10 = 2 × 5
5 = 5 × 1

This structure—called a canonical coin system or greedy-compatible system—ensures that using larger coins first never blocks the optimal solution.

When Greedy Fails:

Consider the non-canonical coin system: {1, 3, 4} with target amount 6.

Greedy Approach

•Target: 6, Coins: {1, 3, 4}
•Take largest coin ≤ 6: coin 4 → remaining: 2
•Take largest coin ≤ 2: coin 1 → remaining: 1
•Take largest coin ≤ 1: coin 1 → remaining: 0
•Greedy uses 3 coins: {4, 1, 1}

Optimal Solution

•Target: 6, Coins: {1, 3, 4}
•Instead of starting with 4...
•Use two 3-cent coins
•3 + 3 = 6 exactly
•Optimal uses 2 coins: {3, 3}

The Structural Failure

More Counterexamples:

Coin System	Target	Greedy Solution	Optimal Solution	Greedy Coins	Optimal Coins
{1, 3, 4}	6	4+1+1	3+3	3	2
{1, 5, 7}	10	7+1+1+1	5+5	4	2
{1, 6, 9}	12	9+1+1+1	6+6	4	2
{1, 3, 9, 10}	28	10+10+3+3+1+1	10+9+9	6	3

The Mathematical Criterion:

A coin system is greedy-compatible (canonical) if and only if, for all amounts n:

Greedy(n) = Optimal(n)

Determining whether a coin system is greedy-compatible is itself a non-trivial problem. For US currency, it can be verified. For arbitrary coin systems, the problem requires analysis.

General Solution - Dynamic Programming: For arbitrary coin systems, the minimum coin change problem requires dynamic programming:

dp[i] = min(dp[i - c] + 1) for all coins c ≤ i

Base case: dp[0] = 0

Time complexity: O(n × k) where k is the number of denominations.

coin_change_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def greedy_coin_change(coins, amount):
    """
    Greedy coin change - works only for canonical coin systems!
    Returns (num_coins, coin_list) or (inf, []) if impossible.
    """
    coins = sorted(coins, reverse=True)  # Sort descending
    result = []
    remaining = amount
    
    for coin in coins:
        while remaining >= coin:
            result.append(coin)
            remaining -= coin
    
    if remaining == 0:
        return len(result), result
    return float('inf'), []
 
def dp_coin_change(coins, amount):
    """
    Dynamic programming coin change - always optimal.
    Time: O(amount * len(coins))
    """
    # dp[i] = (min coins to make amount i, list of coins used)
    dp = [(float('inf'), []) for _ in range(amount + 1)]
    dp[0] = (0, [])
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin][0] + 1 < dp[i][0]:
                dp[i] = (dp[i - coin][0] + 1, dp[i - coin][1] + [coin])
    
    return dp[amount]
 
# Test cases demonstrating greedy failures
test_cases = [
    ({'coins': [1, 3, 4], 'amount': 6}),
    ({'coins': [1, 5, 7], 'amount': 10}),
    ({'coins': [1, 6, 9], 'amount': 12}),
    ({'coins': [1, 3, 9, 10], 'amount': 28}),
]
 
print("Demonstrating Greedy Failures in Coin Change:
")
for tc in test_cases:
    coins, amount = tc['coins'], tc['amount']
    greedy_num, greedy_coins = greedy_coin_change(coins, amount)
    optimal_num, optimal_coins = dp_coin_change(coins, amount)
    
    print(f"Coins: {coins}, Amount: {amount}")
    print(f"  Greedy:  {greedy_num} coins -> {greedy_coins}")
    print(f"  Optimal: {optimal_num} coins -> {optimal_coins}")
    status = "✓ Same" if greedy_num == optimal_num else f"✗ Greedy uses {greedy_num - optimal_num} extra coins"
    print(f"  Result:  {status}
")

Classic Failure #3: Shortest Paths with Negative Edge Weights

Why Dijkstra Fails:

Dijkstra's greedy choice is: "The unvisited vertex with the smallest current distance IS the shortest path to that vertex."

This relies on a critical assumption: relaxing edges can only decrease distances, and once we've found the shortest path to a vertex, no later path can improve it.

Concrete Counterexample:

Consider this graph with vertices A, B, C and edges:

A → B: weight 1
A → C: weight 5
B → C: weight -10

We want the shortest path from A to C.

Dijkstra's Execution:

Initialize: dist[A] = 0, dist[B] = ∞, dist[C] = ∞
Process A (smallest distance): Update dist[B] = 1, dist[C] = 5
Process B (dist=1 < dist[C]=5): Update dist[C] = 1 + (-10) = -9
Process C: Nothing to update

Result: dist[C] = -9 ✓ (Happens to be correct!)

But the issue is order dependency. If we slightly modify the algorithm's tie-breaking or structure, or use certain implementations, the result can be wrong.

A Clearer Failure Case:

Consider this graph:

A → B: weight 2
A → C: weight 4
B → D: weight 1
C → D: weight -5
C → B: weight -3

Shortest path from A to D:

Dijkstra's Execution:

dist[A]=0. Process A: dist[B]=2, dist[C]=4
dist[B]=2 is minimum. Process B: dist[D]=3. Mark B as finalized.
dist[D]=3 is minimum. Process D. Mark D as finalized with dist=3.
dist[C]=4 is minimum. Process C:
- C → D would give 4 + (-5) = -1, but D is already finalized!
- C → B would give 4 + (-3) = 1, but B is already finalized!

Dijkstra returns dist[D] = 3

Actual Shortest Path: A → C → D with weight 4 + (-5) = -1, or A → C → B → D with weight 4 + (-3) + 1 = 2

Both are shorter than 3!

The Core Issue

Correct Algorithms for Negative Edges:

1. Bellman-Ford Algorithm

Relaxes ALL edges V-1 times
No greedy commitment—every edge is reconsidered multiple times
Time complexity: O(V × E)
Can also detect negative cycles

2. SPFA (Shortest Path Faster Algorithm)

Queue-based variant of Bellman-Ford
Only re-relaxes vertices whose distances have changed
Empirically faster on many graphs, but worst-case is still O(V × E)

Shortest Path Algorithm Comparison
Algorithm	Greedy?	Negative Edges?	Negative Cycles?	Time Complexity
Dijkstra	Yes	No ✗	No	O((V+E) log V)
Bellman-Ford	No	Yes ✓	Detects	O(V × E)
Floyd-Warshall	No (DP)	Yes ✓	Detects	O(V³)
Johnson's	Mixed	Yes ✓	No (fails)	O(V² log V + VE)

Classic Failure #4: Weighted Independent Set

Problem Statement: Given a graph G = (V, E) where each vertex v has a weight w(v), find a subset S ⊆ V such that:

S is an independent set (no two vertices in S are adjacent)
The total weight Σw(v) for v ∈ S is maximized

Greedy Strategy: A natural greedy approach: repeatedly select the highest-weight vertex that doesn't conflict with already-selected vertices.

Counterexample:

Consider a path graph with 4 vertices:

A(weight=10) — B(weight=20) — C(weight=20) — D(weight=10)

Edges connect adjacent vertices: A-B, B-C, C-D.

Greedy by Maximum Weight:

Select B (weight=20, highest)
A and C are now blocked (adjacent to B)
Select D (weight=10, only remaining non-blocked vertex)

Greedy Solution: {B, D} with total weight = 30

Optimal Solution:

Select A and C: they are not adjacent (B separates them)
{A, C} with total weight = 10 + 20 = 30

Wait, same weight! Let's try a different example:

A(weight=5) — B(weight=100) — C(weight=100) — D(weight=5)

Greedy:

Select B (weight=100)
A and C blocked
Select D (weight=5)

Greedy: {B, D} = 105

Optimal:

{B} alone = 100 (not better)
{A, C} = 5 + 100 = 105 (same)

Let's be more precise:

A(weight=1) — B(weight=1000) — C(weight=1000) — D(weight=1)

Greedy:

Select B (weight=1000)
A and C blocked
Select D (weight=1)

Greedy: {B, D} = 1001

But we could select {A, C} = 1 + 1000 = 1001 — still the same!

The issue is that for path graphs, dynamic programming gives optimal solutions efficiently, and greedy happens to work reasonably well. Let's try a star graph instead.

Star Graph Counterexample:

Consider a star graph with center vertex X connected to leaves L₁, L₂, L₃, L₄, L₅:

        L₁(weight=10)
        |
        X(weight=15) — L₂(weight=10)
       /|
      L₃ L₄ L₅
   (weight=10 each)

All leaves have weight 10, center has weight 15.

Greedy by Maximum Weight:

Select X (weight=15, highest)
All leaves L₁, L₂, L₃, L₄, L₅ are now blocked (adjacent to X)

Greedy: {X} = 15

Optimal:

Select all leaves: {L₁, L₂, L₃, L₄, L₅}
No two leaves are adjacent (they only connect to X)
Total weight = 10 × 5 = 50

Greedy achieves only 30% of optimal!

The Structural Failure

General Graph Complexity:

The Weighted Independent Set problem on general graphs is NP-hard. There is no known polynomial-time algorithm, and greedy provides no approximation guarantee.

Special Cases:

Tree graphs: DP gives O(n) optimal solution
Bipartite graphs: Still NP-hard
Interval graphs: Greedy DOES work (this is the activity selection problem!)
Chordal graphs: DP/greedy combinations work

Classic Failure #5: The Traveling Salesman Problem

Problem Statement: Given n cities and distances d(i,j) between each pair, find the shortest tour that visits every city exactly once and returns to the starting city.

Greedy Heuristics:

Nearest Neighbor: From the current city, go to the closest unvisited city.
Nearest Insertion: Build a tour by repeatedly inserting the city that causes minimum increase.
Greedy Edge: Add edges in order of increasing length, skipping edges that would create a cycle (before all cities are visited) or degree > 2.

Nearest Neighbor Counterexample:

Consider 4 cities with distances:

	A	B	C	D
A	0	1	10	10
B	1	0	10	2
C	10	10	0	1
D	10	2	1	0

Nearest Neighbor from A:

A → B (distance 1, closest)
B → D (distance 2, closest unvisited)
D → C (distance 1, only option)
C → A (distance 10, return)

Greedy Tour: A → B → D → C → A = 1 + 2 + 1 + 10 = 14

Actually, for this specific example, greedy ties with optimal. Let's construct a worse case.

Classic TSP Greedy Failure:

Consider 5 cities arranged adversarially:

    B
   /|
  1 | 1
 /  |  
A---+---C
 \  |  /
  1 | 1
   \|/
    D
    |
   100
    |
    E

Distances:

A-B: 1, A-C: 2, A-D: 1
B-C: 1, B-D: 100
C-D: 1
D-E: 100
Others: all 100

Nearest Neighbor from A:

A → B (1) or A → D (1) — say A → B
B → C (1)
C → D (1)
D → E (100) — only unvisited
E → A (100) — return

Greedy: 1 + 1 + 1 + 100 + 100 = 203

Optimal Tour: A → D → E → C → B → A But wait, we need all distances...

The key insight is that nearest neighbor can get "trapped" by short local edges and forced into long edges at the end. A more careful tour ordering can avoid the long edges.

Competitive Ratio: The nearest neighbor heuristic can be a factor of O(log n) worse than optimal. No greedy heuristic for TSP has a constant approximation ratio unless P = NP.

The Fundamental Limitation

TSP Solution Approaches
Method	Type	Guarantee	Complexity
Brute Force	Exact	Optimal	O(n!)
Dynamic Programming	Exact	Optimal	O(n² × 2ⁿ)
Branch & Bound	Exact	Optimal	Exponential (pruned)
Nearest Neighbor	Greedy	O(log n) approx	O(n²)
Christofides	Approximation	1.5× approx	O(n³)
Lin-Kernighan	Local Search	Empirically good	Variable

Pattern Recognition: When to Suspect Greedy Will Fail

After examining these classic failures, clear patterns emerge. Here is a checklist for recognizing when greedy is likely to fail:

Warning Signs That Greedy Will Fail

•Discrete all-or-nothing choices — When items must be taken entirely or not at all (0/1 decisions), greedy commitments foreclose combinations that might be superior.
•Non-canonical number systems — When denomination/value structures don't align hierarchically, smaller components can combine more efficiently than larger ones taken greedily.
•Negative values or decreasing costs — When costs can decrease as you proceed, early commitments become premature. Greedy can't anticipate future discounts.
•High vertex degrees / many conflicts — In graph problems, high-degree vertices block many options. Taking them greedily might exclude collectively superior alternatives.
•Closed cycles or return constraints — When solutions must form cycles (like TSP), early choices affect end-game options in ways greedy cannot foresee.
•Overlapping subproblems — When the same subproblem appears with different contexts, greedy's lack of memory causes redundant or inconsistent decisions.
•Multi-objective optimization — When multiple criteria must be balanced, greedy optimization of one criterion can sabotage others.
•The problem is NP-hard — Most NP-hard optimization problems cannot be solved optimally by greedy (though greedy heuristics may yield acceptable approximations).

The Litmus Test

Summary: Classic Greedy Failure Cases

We have examined the most instructive cases where greedy algorithms fail to produce optimal solutions. Each failure illuminates a fundamental limitation of the greedy paradigm:

Summary of Classic Greedy Failures
Problem	Why Greedy Fails	Correct Approach
0/1 Knapsack	Discrete choices foreclose optimal combinations	Dynamic Programming O(nW)
Coin Change (non-canonical)	Smaller coins combine more efficiently	Dynamic Programming O(nk)
Shortest Paths (negative edges)	Early finalization misses later improvements	Bellman-Ford O(VE)
Weighted Independent Set	High-degree vertices block superior alternatives	DP on trees; NP-hard generally
Traveling Salesman	Early edges force bad closing edges	DP O(n²2ⁿ); approximations

Page Complete