When Greedy Fails - Learning Module

Loading content...

0/276

Counterexamples for Wrong Greedy

The Art of Breaking Algorithms

In the previous page, we cataloged classic problems where greedy fails. But in practice, you'll encounter new problems—problems that don't appear in textbooks, problems where you've invented a greedy strategy and need to verify whether it works.

How do you know if your greedy algorithm is correct? You have two options:

Prove it correct — Demonstrate the greedy choice property and optimal substructure hold.
Disprove it with a counterexample — Find a single input where greedy produces a suboptimal answer.

This page focuses on the second skill: the systematic construction of counterexamples. This is not merely a debugging technique—it's a fundamental algorithmic skill that develops your intuition for problem structure and safeguards you from deploying incorrect solutions.

What You Will Learn

By the end of this page, you will be able to systematically construct counterexamples that break incorrect greedy algorithms, understand the adversarial mindset required for counterexample generation, and apply structured techniques to expose greedy failures in novel problems.

A Crucial Asymmetry

Proving correctness is hard—you must show the algorithm works for ALL inputs. Finding a counterexample is easier—you only need ONE input where it fails. But "easier" doesn't mean "easy." Counterexamples for subtle algorithms can be deceptively hard to construct.

The Adversarial Mindset

Constructing counterexamples requires a fundamental shift in perspective. Instead of asking "How would I solve this problem?", you must ask "How can I construct an input where the greedy approach takes a wrong turn?"

This is adversarial thinking. You are the antagonist trying to break the algorithm. You control the input and can craft it maliciously to exploit the algorithm's blind spots.

The Greedy Algorithm's Vulnerabilities:

Every greedy algorithm has the same structural weakness: it makes irrevocable decisions based on incomplete information. Your goal as an adversary is to:

Identify what information the greedy algorithm ignores
Construct an input where that ignored information is crucial
Show that the greedy decision leads to a dead end or suboptimal path

Adversarial Thinking Principles

•Exploit Local Blindness — Greedy only sees the current state. Create inputs where short-term gains cause long-term losses.
•Create Conflicting Hierarchies — Make the 'best' choice by one metric (e.g., value) conflict with the 'best' by another (e.g., capacity usage).
•Use Blocking — Design an item/choice that looks attractive but blocks access to multiple better items.
•Engineer Tight Constraints — Make capacity or resource constraints such that greedy's first choice leaves no room for the optimal combination.
•Exploit Threshold Effects — Create inputs where greedy falls just short of a threshold that would unlock a much better solution.
•Delay the Sting — Construct inputs where the greedy choice seems fine initially but causes problems only at the very end.

The Minimal Counterexample

Always aim for the SMALLEST counterexample possible. A counterexample with 3 items is more convincing and debuggable than one with 100 items. Start small: can you break the algorithm with 2 items? 3? Find the minimal structure that causes failure.

The Systematic Counterexample Construction Process

Rather than relying on pure intuition, follow this structured process to generate counterexamples systematically:

The 5-Step Counterexample Process

•Identify the Greedy Criterion — What rule does the algorithm use to make each choice? (e.g., maximum value, minimum weight, best ratio, earliest deadline)
•Identify What's Ignored — What information does this criterion NOT consider? What could go wrong because of this blind spot?
•Create the "Trap" Item — Design an item/choice that scores best on the greedy criterion but leads to a dead end or blocks optimal alternatives.
•Create the "Hidden Gem" Alternative — Design items that score worse on the greedy criterion but would lead to a globally optimal solution if chosen instead of the trap.
•Verify with Calculation — Execute the greedy algorithm on your input, compute the optimal solution separately, and confirm greedy is suboptimal.

Worked Example: Breaking a Task Scheduling Greedy

Suppose you've designed a greedy algorithm for task scheduling:

Each task has a profit and a deadline
You can complete at most one task per time slot
You want to maximize profit

Proposed Greedy: Always select the highest-profit unscheduled task that can still meet its deadline.

Let's try to break it:

Step 1: Identify the Greedy Criterion

The algorithm sorts by profit (descending) and greedily assigns tasks.

Step 2: Identify What's Ignored

The algorithm ignores deadline flexibility. A high-profit task with a late deadline is treated the same as a high-profit task with an early deadline. But early-deadline tasks constrain scheduling more.

Step 3: Create the Trap

Create a high-profit task with an early deadline that, if taken, blocks other valuable tasks.

Task A: Profit = 100, Deadline = 1 (must be done in slot 1)

Step 4: Create the Hidden Gem Alternative

Task B: Profit = 60, Deadline = 2 (can be done in slot 1 or 2)
Task C: Profit = 60, Deadline = 2 (can be done in slot 1 or 2)

Step 5: Verify

Greedy Execution:

Schedule Task A in slot 1 (profit = 100) — highest profit
Tasks B and C both have deadline 2, but slot 1 is taken
Only one of B or C can be scheduled in slot 2
Schedule B in slot 2 (profit = 60)

Greedy total: 100 + 60 = 160

Optimal:

Don't take A. Schedule B in slot 1, C in slot 2.
Total profit: 60 + 60 = 120

Wait, greedy wins! Let's adjust:

Task A: Profit = 50, Deadline = 1
Task B: Profit = 40, Deadline = 2
Task C: Profit = 40, Deadline = 2

Greedy: A + B = 50 + 40 = 90 Optimal: B + C = 40 + 40 = 80

Greedy still wins... The issue is that profit-based greedy actually works for this problem variant! This is a case where our counterexample attempt reveals the algorithm might be correct. Let's try a different attack.

Refined Attack:

Consider tasks with both profits AND weights, where we maximize profit/weight ratio... Actually, let's attack a simpler target: greedy sorted by deadline alone (earliest deadline first).

Task A: Profit = 1, Deadline = 1
Task B: Profit = 100, Deadline = 2

Greedy (earliest deadline):

Schedule A in slot 1
Schedule B in slot 2

Total: 101 — This is optimal!

Let's try:

Task A: Profit = 1, Deadline = 1
Task B: Profit = 100, Deadline = 1
Task C: Profit = 1, Deadline = 2

Greedy (earliest deadline first): Both A and B have deadline 1. If we tie-break arbitrarily, say we take A:

Schedule A in slot 1
Can't schedule B (deadline 1 but slot 1 taken)
Schedule C in slot 2

Greedy Total: 1 + 1 = 2

Optimal: Take B in slot 1, C in slot 2 Optimal Total: 100 + 1 = 101

Counterexample found! The earliest-deadline greedy ignores profit, leading to arbitrarily bad solutions.

Counterexample Success

We successfully broke the earliest-deadline-first greedy. The counterexample is minimal (3 tasks) and demonstrates the flaw clearly: greedy ignores profit entirely, taking a profit-1 task over a profit-100 task simply because of an arbitrary tie-break.

Common Counterexample Patterns

Certain counterexample structures appear repeatedly across different greedy algorithms. Recognizing these patterns accelerates counterexample construction.

Pattern 1: The Blocker

Structure: One item that looks attractive but, if taken, blocks multiple better items.

Template:

Blocker item: Score highly on greedy metric, uses up key resource
Blocked items: Score lower individually but collectively superior

Example (Interval Scheduling):

Suppose greedy picks the longest interval first.

Blocker:   [=========long interval=========]  (length 10)
Blocked 1: [--]                               (length 2)
Blocked 2:     [--]                           (length 2)
Blocked 3:         [--]                       (length 2)
Blocked 4:             [--]                   (length 2)
Blocked 5:                 [--]               (length 2)

Greedy takes the length-10 blocker (1 interval). Optimal takes all five short intervals (5 intervals).

Counterexample! Longest-first greedy fails for interval scheduling.

Pattern 2: The Capacity Trap

Structure: Greedy fills capacity with one 'good' item, leaving no room for the optimal combination.

Template:

Trap item: High value, high weight (fills most of capacity)
Optimal items: Lower individual values/weights but combine perfectly

Example (Knapsack with capacity 10):

Trap: Weight 6, Value 30, Ratio 5.0
Optimal A: Weight 5, Value 28, Ratio 5.6
Optimal B: Weight 5, Value 28, Ratio 5.6

Greedy by ratio: Takes A (ratio 5.6), then Trap doesn't fit (6 > 5 remaining), B doesn't fit (5 = 5, taking B), leaving capacity 0.

Actually greedy by ratio takes A=28, then considers B with 5 capacity remaining, and B fits! Total = 56.

Let's fix:

Trap: Weight 7, Value 35, Ratio 5.0
Optimal A: Weight 5, Value 26, Ratio 5.2
Optimal B: Weight 5, Value 26, Ratio 5.2

Greedy by ratio: Takes A (ratio 5.2), remaining capacity = 5, B fits (ratio 5.2), total = 52. Trap alternative: Take Trap (weight 7, value 35), remaining = 3, neither A nor B fits. Total = 35.

Greedy wins here too. The 0/1 knapsack is surprisingly robust against simple counterexamples. Let's try the canonical one:

A: Weight 10, Value 60, Ratio 6.0
B: Weight 20, Value 100, Ratio 5.0
C: Weight 30, Value 120, Ratio 4.0
Capacity: 50

Greedy by ratio: A (60, cap=40), B (100, cap=20), C doesn't fit. Total = 160. Optimal: B + C = 220.

Here's the counterexample!

The Capacity Trap Formula

To construct a capacity trap: make the trap item have excellent ratio but awkward size, and make optimal items have slightly worse ratios but sizes that combine perfectly to fill capacity. The key is sizing the trap to leave insufficient room for alternatives.

Pattern 3: The Delayed Payoff

Structure: A short-term sacrifice enables a long-term gain that greedy cannot foresee.

Template:

Greedy path: Good early, forced bad ending
Optimal path: Mediocre early, excellent ending

Example (Path Selection):

Find shortest path A → D:

    1        100
A ----→ B -------→ D
 |               ↗
 |              /
 10     1     /
 |     C ----
 |    ↗
 +---

Edges: A→B (weight 1), B→D (weight 100), A→C (weight 10), C→D (weight 1)

Greedy (at each step, take shortest edge):

At A: B is closer (1 < 10), go to B
At B: Only option is D (100)
Path: A → B → D, total = 101

Optimal:

A → C → D = 10 + 1 = 11

The short-term sacrifice (taking the longer A→C edge) enables the much shorter C→D edge. Greedy's commitment to A→B forecloses this path.

Pattern 4: The Denomination Mismatch

Structure: Greedy picks the largest unit, but smaller units combine more efficiently.

Template:

Large denomination: Big but leaves awkward remainder
Small denominations: Combine cleanly to target

Example (Coin Change with {1, 3, 4}, target = 6):

Greedy: 4 + 1 + 1 = 3 coins Optimal: 3 + 3 = 2 coins

The denominations 3 and 3 cover the target exactly, while 4 leaves remainder 2 that requires two 1s.

Pattern 5: The High-Degree Hub

Structure: In graph problems, a high-degree vertex looks valuable but blocks many neighbors.

Template:

Hub: Central vertex connected to many neighbors
Leaves: Collectively more valuable than hub alone

Example (Vertex Cover selecting min-degree vertices first):

Star graph: Center X connected to leaves A, B, C, D, E.

Greedy (min degree): Select all leaves (degree 1 each) → 5 vertices Optimal: Select only X → 1 vertex covers all edges

Or for Maximum Independent Set (max weight, as we saw):

Hub X (weight 15), Leaves A-E (weight 10 each).

Greedy (max weight): Select X → total 15 Optimal: Select all leaves → total 50

Verifying Counterexamples Rigorously

A counterexample is only valid if:

The input satisfies all problem constraints
The greedy algorithm's execution is traced correctly
There exists a valid alternative solution
The alternative solution is strictly better

Let's formalize the verification process:

Counterexample Verification Checklist

•Constraint Check — Verify the input is a valid instance. All items have positive weights? Target is positive? Graph is connected (if required)? No constraints violated.
•Greedy Trace — Execute the greedy algorithm step by step. At each step, verify the greedy choice matches the algorithm's defined criterion. Don't assume—trace explicitly.
•Feasibility Check — Verify the 'optimal' solution you're comparing against is actually valid. Does it satisfy all constraints? Is it a legal solution to the problem?
•Strict Improvement — Confirm the alternative is STRICTLY better, not just equal. If they're equal, you haven't found a counterexample—you've found a tie.
•Minimality Check — Attempt to reduce the counterexample. Can you remove an item and still have a counterexample? Minimal counterexamples are more convincing.

verify_counterexample.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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def verify_knapsack_counterexample():
    """
    Rigorous verification of the 0/1 knapsack counterexample.
    """
    # Input definition
    items = [
        {'name': 'A', 'weight': 10, 'value': 60},
        {'name': 'B', 'weight': 20, 'value': 100},
        {'name': 'C', 'weight': 30, 'value': 120},
    ]
    capacity = 50
    
    # Step 1: Constraint Check
    print("=== Step 1: Constraint Verification ===")
    for item in items:
        assert item['weight'] > 0, f"{item['name']} has non-positive weight"
        assert item['value'] > 0, f"{item['name']} has non-positive value"
    assert capacity > 0, "Capacity must be positive"
    print("✓ All constraints satisfied\n")
    
    # Step 2: Greedy Execution Trace
    print("=== Step 2: Greedy Algorithm Trace ===")
    # Sort by value/weight ratio (descending)
    sorted_items = sorted(items, key=lambda x: x['value']/x['weight'], reverse=True)
    print("Items sorted by ratio (descending):")
    for item in sorted_items:
        ratio = item['value'] / item['weight']
        print(f"  {item['name']}: value={item['value']}, weight={item['weight']}, ratio={ratio:.2f}")
    
    greedy_selection = []
    greedy_weight = 0
    greedy_value = 0
    remaining_capacity = capacity
    
    print(f"\nGreedy execution (capacity = {capacity}):")
    for item in sorted_items:
        if item['weight'] <= remaining_capacity:
            greedy_selection.append(item['name'])
            greedy_weight += item['weight']
            greedy_value += item['value']
            remaining_capacity -= item['weight']
            print(f"  TAKE {item['name']}: weight={item['weight']}, value={item['value']}, remaining={remaining_capacity}")
        else:
            print(f"  SKIP {item['name']}: weight={item['weight']} > remaining={remaining_capacity}")
    
    print(f"\nGreedy result: {greedy_selection}, total value = {greedy_value}\n")
    
    # Step 3: Alternative Solution Feasibility
    print("=== Step 3: Alternative Solution Verification ===")
    alternative_selection = ['B', 'C']
    alternative_items = [item for item in items if item['name'] in alternative_selection]
    alternative_weight = sum(item['weight'] for item in alternative_items)
    alternative_value = sum(item['value'] for item in alternative_items)
    
    print(f"Alternative selection: {alternative_selection}")
    print(f"  Total weight: {alternative_weight}")
    print(f"  Total value: {alternative_value}")
    
    assert alternative_weight <= capacity, "Alternative exceeds capacity!"
    print(f"✓ Alternative weight {alternative_weight} ≤ capacity {capacity}\n")
    
    # Step 4: Strict Improvement Check
    print("=== Step 4: Improvement Verification ===")
    print(f"Greedy value: {greedy_value}")
    print(f"Alternative value: {alternative_value}")
    
    if alternative_value > greedy_value:
        improvement = alternative_value - greedy_value
        pct = (alternative_value / greedy_value - 1) * 100
        print(f"✓ Alternative is STRICTLY BETTER by {improvement} ({pct:.1f}% improvement)")
        print("\n=== COUNTEREXAMPLE VERIFIED ===")
    else:
        print("✗ Not a valid counterexample")
 
if __name__ == "__main__":
    verify_knapsack_counterexample()

When You Can't Find a Counterexample

What if you've tried multiple counterexample patterns and none of them work? This can indicate one of several situations:

When Counterexamples Prove Elusive

•The algorithm might be correct — Perhaps greedy actually works for this problem. The greedy choice property may hold. Time to attempt a proof.
•The counterexample requires rare structure — Some failures only occur with very specific input configurations. Try more extreme cases: very large/small values, many duplicates, special graph structures.
•The counterexample is large — Some greedy algorithms fail only for k ≥ 4 items or n ≥ 10 vertices. Try larger inputs systematically.
•You're attacking the wrong vulnerability — Revisit Step 2. What information does greedy ignore? Are you exploiting that correctly?
•Random testing can help — Generate many random inputs, run both greedy and optimal solver (brute-force for small inputs), and look for discrepancies.

The Bridge to Proofs:

Failing to find a counterexample after substantial effort is evidence (but not proof) that greedy might work. At this point, shift your approach:

State the greedy choice property precisely — What exactly is the claim that the first greedy choice is safe?
Attempt an exchange argument — If we had an optimal solution that didn't start with the greedy choice, can we exchange to get one that does without loss of quality?
Verify optimal substructure — After making the greedy choice, is the remaining problem a smaller instance of the same problem?

If you can establish these, the greedy algorithm is correct. If you find a gap in the proof logic, that gap often points directly to a counterexample structure.

The Duality Principle

Counterexample construction and proof construction are dual activities. Every failed proof attempt suggests where to look for counterexamples. Every failed counterexample attempt suggests that the proof might succeed. Alternate between the two approaches to maximize insight.

random_counterexample_search.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
63
64
65
66
67
68
69
70
71
import random
from itertools import combinations
 
def greedy_knapsack(items, capacity):
    """Greedy by value/weight ratio."""
    sorted_items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    total_weight = 0
    for weight, value in sorted_items:
        if total_weight + weight <= capacity:
            total_value += value
            total_weight += weight
    return total_value
 
def optimal_knapsack(items, capacity):
    """Brute-force optimal (exponential, for small inputs only)."""
    best = 0
    for r in range(len(items) + 1):
        for subset in combinations(items, r):
            total_weight = sum(item[0] for item in subset)
            total_value = sum(item[1] for item in subset)
            if total_weight <= capacity and total_value > best:
                best = total_value
    return best
 
def search_for_counterexamples(num_trials=10000, max_items=5, max_weight=20, max_value=100, max_capacity=50):
    """
    Randomly generate inputs and check if greedy ever fails.
    """
    counterexamples_found = []
    
    for trial in range(num_trials):
        # Generate random items
        n_items = random.randint(2, max_items)
        items = [(random.randint(1, max_weight), random.randint(1, max_value)) 
                 for _ in range(n_items)]
        capacity = random.randint(1, max_capacity)
        
        greedy_result = greedy_knapsack(items, capacity)
        optimal_result = optimal_knapsack(items, capacity)
        
        if greedy_result < optimal_result:
            counterexamples_found.append({
                'items': items,
                'capacity': capacity,
                'greedy': greedy_result,
                'optimal': optimal_result,
                'gap': optimal_result - greedy_result
            })
    
    print(f"Searched {num_trials} random inputs")
    print(f"Found {len(counterexamples_found)} counterexamples")
    
    if counterexamples_found:
        # Show the smallest counterexample
        smallest = min(counterexamples_found, key=lambda x: len(x['items']))
        print(f"\nSmallest counterexample:")
        print(f"  Items (weight, value): {smallest['items']}")
        print(f"  Capacity: {smallest['capacity']}")
        print(f"  Greedy value: {smallest['greedy']}")
        print(f"  Optimal value: {smallest['optimal']}")
        
        # Show the largest gap
        worst = max(counterexamples_found, key=lambda x: x['gap'])
        print(f"\nLargest gap counterexample:")
        print(f"  Items: {worst['items']}")
        print(f"  Capacity: {worst['capacity']}")
        print(f"  Greedy: {worst['greedy']}, Optimal: {worst['optimal']}, Gap: {worst['gap']}")
 
if __name__ == "__main__":
    search_for_counterexamples()

Counterexamples in Technical Interviews

In technical interviews, counterexample construction is both a debugging tool and a demonstration of algorithmic sophistication. Interviewers are often more impressed by a candidate who can articulate why their initial greedy approach fails than by one who stumbles onto the right algorithm with no understanding of alternatives.

Scenario: You're solving a problem and propose a greedy approach. The interviewer asks: "Are you sure that works?"

This is your cue to do one of two things:

Provide a convincing correctness argument (greedy choice property + optimal substructure)
Find a counterexample and pivot to a correct approach

Interview Best Practices

•Verbalize your process — 'Let me try to break my greedy with a small example...' shows methodical thinking.
•Start minimal — 'What if there are just 2 items?' Then expand: 'What about 3 items?'
•Identify the greedy criterion explicitly — 'My greedy picks by maximum profit. What if that conflicts with...'
•When you find a counterexample, explain why it works — 'This breaks because the greedy picks A, but A blocks access to B and C which are collectively better.'
•Pivot confidently — 'Since greedy doesn't work, this has overlapping subproblems, so let me try dynamic programming.'
•If greedy is correct, explain why — 'The greedy choice is safe because we can always exchange any optimal solution's first choice with ours without loss.'

The Interviewer's Perspective

Strong candidates don't just solve problems—they demonstrate understanding of WHY their solution works. Finding a counterexample to disprove a wrong approach is as valuable as finding the right approach. It shows you can self-correct and have deep algorithmic intuition.

Common Interview Problem Types Where Greedy Fails (and candidates often try it):

Problem	Common (Wrong) Greedy	Why It Fails	Correct Approach
Coin Change	Largest coin first	Non-canonical coins	DP
0/1 Knapsack	Best ratio first	Discrete choices	DP
Longest Increasing Subsequence	Greedy extend	Can't undo past choices	DP
Edit Distance	Greedy match	Needs optimal alignment	DP
Partition Equal Subset	Greedy fit	Subset sum is NP-hard	DP
Word Break	Greedy longest match	Can block valid breaks	DP/Backtracking

Knowing these patterns helps you avoid greedy traps and quickly pivot to correct approaches.

Advanced: Systematic Adversarial Input Generation

Beyond manual counterexample construction, experienced algorithm designers use systematic techniques to generate adversarial inputs. These techniques are particularly useful when testing algorithm implementations for edge cases.

Technique 1: Boundary Value Analysis

Greedy algorithms often have decision boundaries. Construct inputs that sit exactly on these boundaries:

If greedy compares ratios, create items with equal ratios
If greedy uses thresholds, place values at exactly the threshold
If greedy has tie-breaking rules, create ties that exercise the tie-breaker

Technique 2: Extremal Inputs

Push parameters to extremes:

Single item — Does greedy work when there's only one choice?
Maximum capacity — What if capacity equals total item weight?
Zero capacity — Edge case for resource-constrained problems
All equal — All items have the same value/weight/priority
Sorted inputs — Already sorted ascending, descending, or by the greedy criterion
Anti-sorted — Sorted opposite to the greedy criterion

Technique 3: Parameterized Construction

Create a family of inputs controlled by a parameter k:

For k from 2 to 10:
  Create k small items that collectively beat one large item
  Run greedy and check if it picks the large item wrongly

This helps find the minimum k where greedy fails.

Technique 4: Inverse Engineering

Start with the solution and work backward:

Define an optimal solution S* that you know is correct
Identify what greedy would choose first instead of S*'s first element
Set parameters so that greedy's choice has slightly better local score
Verify that S* is globally better despite worse first choice

Example: For interval scheduling, if optimal selects intervals {A, B, C}:

Create a competing interval D that starts earliest (greedy criterion)
Make D overlap with all of A, B, C
Make A, B, C non-overlapping with each other
Greedy picks D (1 interval), optimal picks {A, B, C} (3 intervals)

Computational Adversarial Testing

In competitive programming and software testing, 'stress testing' generates thousands of random inputs and compares the output of a suspected-correct algorithm against a known-correct (but slower) algorithm. Any discrepancy immediately yields a counterexample for debugging.

Summary: Counterexample Construction

Constructing counterexamples is a fundamental skill that separates novice problem-solvers from experts. We've covered the complete methodology:

Key Takeaways

•Adopt the adversarial mindset — Think like an attacker trying to break the algorithm. You control the input.
•Follow the systematic 5-step process — Identify criterion, identify ignored information, create trap, create alternative, verify.
•Recognize common patterns — Blocker, capacity trap, delayed payoff, denomination mismatch, high-degree hub.
•Verify rigorously — Check constraints, trace execution, confirm feasibility, prove strict improvement.
•Know when to pivot — If counterexamples prove elusive, attempt a correctness proof instead.
•Practice in interviews — Articulating why greedy fails demonstrates deep algorithmic understanding.
•Use systematic generation — Boundary values, extremes, parameterized families, and inverse engineering.

Page Complete

You now possess the tools to systematically break incorrect greedy algorithms. The next page will cover the complementary skill: recognizing when greedy IS applicable and how to identify problems with the greedy choice property.

Counterexamples for Wrong Greedy

The Art of Breaking Algorithms

How do you know if your greedy algorithm is correct? You have two options:

Prove it correct — Demonstrate the greedy choice property and optimal substructure hold.
Disprove it with a counterexample — Find a single input where greedy produces a suboptimal answer.

What You Will Learn

A Crucial Asymmetry

The Adversarial Mindset

This is adversarial thinking. You are the antagonist trying to break the algorithm. You control the input and can craft it maliciously to exploit the algorithm's blind spots.

The Greedy Algorithm's Vulnerabilities:

Every greedy algorithm has the same structural weakness: it makes irrevocable decisions based on incomplete information. Your goal as an adversary is to:

Identify what information the greedy algorithm ignores
Construct an input where that ignored information is crucial
Show that the greedy decision leads to a dead end or suboptimal path

Adversarial Thinking Principles

•Exploit Local Blindness — Greedy only sees the current state. Create inputs where short-term gains cause long-term losses.
•Create Conflicting Hierarchies — Make the 'best' choice by one metric (e.g., value) conflict with the 'best' by another (e.g., capacity usage).
•Use Blocking — Design an item/choice that looks attractive but blocks access to multiple better items.
•Engineer Tight Constraints — Make capacity or resource constraints such that greedy's first choice leaves no room for the optimal combination.
•Exploit Threshold Effects — Create inputs where greedy falls just short of a threshold that would unlock a much better solution.
•Delay the Sting — Construct inputs where the greedy choice seems fine initially but causes problems only at the very end.

The Minimal Counterexample

The Systematic Counterexample Construction Process

Rather than relying on pure intuition, follow this structured process to generate counterexamples systematically:

The 5-Step Counterexample Process

•Identify the Greedy Criterion — What rule does the algorithm use to make each choice? (e.g., maximum value, minimum weight, best ratio, earliest deadline)
•Identify What's Ignored — What information does this criterion NOT consider? What could go wrong because of this blind spot?
•Create the "Trap" Item — Design an item/choice that scores best on the greedy criterion but leads to a dead end or blocks optimal alternatives.
•Create the "Hidden Gem" Alternative — Design items that score worse on the greedy criterion but would lead to a globally optimal solution if chosen instead of the trap.
•Verify with Calculation — Execute the greedy algorithm on your input, compute the optimal solution separately, and confirm greedy is suboptimal.

Worked Example: Breaking a Task Scheduling Greedy

Suppose you've designed a greedy algorithm for task scheduling:

Each task has a profit and a deadline
You can complete at most one task per time slot
You want to maximize profit

Proposed Greedy: Always select the highest-profit unscheduled task that can still meet its deadline.

Let's try to break it:

Step 1: Identify the Greedy Criterion

The algorithm sorts by profit (descending) and greedily assigns tasks.

Step 2: Identify What's Ignored

Step 3: Create the Trap

Create a high-profit task with an early deadline that, if taken, blocks other valuable tasks.

Task A: Profit = 100, Deadline = 1 (must be done in slot 1)

Step 4: Create the Hidden Gem Alternative

Task B: Profit = 60, Deadline = 2 (can be done in slot 1 or 2)
Task C: Profit = 60, Deadline = 2 (can be done in slot 1 or 2)

Step 5: Verify

Greedy Execution:

Schedule Task A in slot 1 (profit = 100) — highest profit
Tasks B and C both have deadline 2, but slot 1 is taken
Only one of B or C can be scheduled in slot 2
Schedule B in slot 2 (profit = 60)

Greedy total: 100 + 60 = 160

Optimal:

Don't take A. Schedule B in slot 1, C in slot 2.
Total profit: 60 + 60 = 120

Wait, greedy wins! Let's adjust:

Task A: Profit = 50, Deadline = 1
Task B: Profit = 40, Deadline = 2
Task C: Profit = 40, Deadline = 2

Greedy: A + B = 50 + 40 = 90 Optimal: B + C = 40 + 40 = 80

Refined Attack:

Consider tasks with both profits AND weights, where we maximize profit/weight ratio... Actually, let's attack a simpler target: greedy sorted by deadline alone (earliest deadline first).

Task A: Profit = 1, Deadline = 1
Task B: Profit = 100, Deadline = 2

Greedy (earliest deadline):

Schedule A in slot 1
Schedule B in slot 2

Total: 101 — This is optimal!

Let's try:

Task A: Profit = 1, Deadline = 1
Task B: Profit = 100, Deadline = 1
Task C: Profit = 1, Deadline = 2

Greedy (earliest deadline first): Both A and B have deadline 1. If we tie-break arbitrarily, say we take A:

Schedule A in slot 1
Can't schedule B (deadline 1 but slot 1 taken)
Schedule C in slot 2

Greedy Total: 1 + 1 = 2

Optimal: Take B in slot 1, C in slot 2 Optimal Total: 100 + 1 = 101

Counterexample found! The earliest-deadline greedy ignores profit, leading to arbitrarily bad solutions.

Counterexample Success

Common Counterexample Patterns

Certain counterexample structures appear repeatedly across different greedy algorithms. Recognizing these patterns accelerates counterexample construction.

Pattern 1: The Blocker

Structure: One item that looks attractive but, if taken, blocks multiple better items.

Template:

Blocker item: Score highly on greedy metric, uses up key resource
Blocked items: Score lower individually but collectively superior

Example (Interval Scheduling):

Suppose greedy picks the longest interval first.

Blocker:   [=========long interval=========]  (length 10)
Blocked 1: [--]                               (length 2)
Blocked 2:     [--]                           (length 2)
Blocked 3:         [--]                       (length 2)
Blocked 4:             [--]                   (length 2)
Blocked 5:                 [--]               (length 2)

Greedy takes the length-10 blocker (1 interval). Optimal takes all five short intervals (5 intervals).

Counterexample! Longest-first greedy fails for interval scheduling.

Pattern 2: The Capacity Trap

Structure: Greedy fills capacity with one 'good' item, leaving no room for the optimal combination.

Template:

Trap item: High value, high weight (fills most of capacity)
Optimal items: Lower individual values/weights but combine perfectly

Example (Knapsack with capacity 10):

Trap: Weight 6, Value 30, Ratio 5.0
Optimal A: Weight 5, Value 28, Ratio 5.6
Optimal B: Weight 5, Value 28, Ratio 5.6

Greedy by ratio: Takes A (ratio 5.6), then Trap doesn't fit (6 > 5 remaining), B doesn't fit (5 = 5, taking B), leaving capacity 0.

Actually greedy by ratio takes A=28, then considers B with 5 capacity remaining, and B fits! Total = 56.

Let's fix:

Trap: Weight 7, Value 35, Ratio 5.0
Optimal A: Weight 5, Value 26, Ratio 5.2
Optimal B: Weight 5, Value 26, Ratio 5.2

Greedy wins here too. The 0/1 knapsack is surprisingly robust against simple counterexamples. Let's try the canonical one:

A: Weight 10, Value 60, Ratio 6.0
B: Weight 20, Value 100, Ratio 5.0
C: Weight 30, Value 120, Ratio 4.0
Capacity: 50

Greedy by ratio: A (60, cap=40), B (100, cap=20), C doesn't fit. Total = 160. Optimal: B + C = 220.

Here's the counterexample!

The Capacity Trap Formula

Pattern 3: The Delayed Payoff

Structure: A short-term sacrifice enables a long-term gain that greedy cannot foresee.

Template:

Greedy path: Good early, forced bad ending
Optimal path: Mediocre early, excellent ending

Example (Path Selection):

Find shortest path A → D:

    1        100
A ----→ B -------→ D
 |               ↗
 |              /
 10     1     /
 |     C ----
 |    ↗
 +---

Edges: A→B (weight 1), B→D (weight 100), A→C (weight 10), C→D (weight 1)

Greedy (at each step, take shortest edge):

At A: B is closer (1 < 10), go to B
At B: Only option is D (100)
Path: A → B → D, total = 101

Optimal:

A → C → D = 10 + 1 = 11

The short-term sacrifice (taking the longer A→C edge) enables the much shorter C→D edge. Greedy's commitment to A→B forecloses this path.

Pattern 4: The Denomination Mismatch

Structure: Greedy picks the largest unit, but smaller units combine more efficiently.

Template:

Large denomination: Big but leaves awkward remainder
Small denominations: Combine cleanly to target

Example (Coin Change with {1, 3, 4}, target = 6):

Greedy: 4 + 1 + 1 = 3 coins Optimal: 3 + 3 = 2 coins

The denominations 3 and 3 cover the target exactly, while 4 leaves remainder 2 that requires two 1s.

Pattern 5: The High-Degree Hub

Structure: In graph problems, a high-degree vertex looks valuable but blocks many neighbors.

Template:

Hub: Central vertex connected to many neighbors
Leaves: Collectively more valuable than hub alone

Example (Vertex Cover selecting min-degree vertices first):

Star graph: Center X connected to leaves A, B, C, D, E.

Greedy (min degree): Select all leaves (degree 1 each) → 5 vertices Optimal: Select only X → 1 vertex covers all edges

Or for Maximum Independent Set (max weight, as we saw):

Hub X (weight 15), Leaves A-E (weight 10 each).

Greedy (max weight): Select X → total 15 Optimal: Select all leaves → total 50

Verifying Counterexamples Rigorously

A counterexample is only valid if:

The input satisfies all problem constraints
The greedy algorithm's execution is traced correctly
There exists a valid alternative solution
The alternative solution is strictly better

Let's formalize the verification process:

Counterexample Verification Checklist

•Constraint Check — Verify the input is a valid instance. All items have positive weights? Target is positive? Graph is connected (if required)? No constraints violated.
•Greedy Trace — Execute the greedy algorithm step by step. At each step, verify the greedy choice matches the algorithm's defined criterion. Don't assume—trace explicitly.
•Feasibility Check — Verify the 'optimal' solution you're comparing against is actually valid. Does it satisfy all constraints? Is it a legal solution to the problem?
•Strict Improvement — Confirm the alternative is STRICTLY better, not just equal. If they're equal, you haven't found a counterexample—you've found a tie.
•Minimality Check — Attempt to reduce the counterexample. Can you remove an item and still have a counterexample? Minimal counterexamples are more convincing.

verify_counterexample.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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
def verify_knapsack_counterexample():
    """
    Rigorous verification of the 0/1 knapsack counterexample.
    """
    # Input definition
    items = [
        {'name': 'A', 'weight': 10, 'value': 60},
        {'name': 'B', 'weight': 20, 'value': 100},
        {'name': 'C', 'weight': 30, 'value': 120},
    ]
    capacity = 50
    
    # Step 1: Constraint Check
    print("=== Step 1: Constraint Verification ===")
    for item in items:
        assert item['weight'] > 0, f"{item['name']} has non-positive weight"
        assert item['value'] > 0, f"{item['name']} has non-positive value"
    assert capacity > 0, "Capacity must be positive"
    print("✓ All constraints satisfied\n")
    
    # Step 2: Greedy Execution Trace
    print("=== Step 2: Greedy Algorithm Trace ===")
    # Sort by value/weight ratio (descending)
    sorted_items = sorted(items, key=lambda x: x['value']/x['weight'], reverse=True)
    print("Items sorted by ratio (descending):")
    for item in sorted_items:
        ratio = item['value'] / item['weight']
        print(f"  {item['name']}: value={item['value']}, weight={item['weight']}, ratio={ratio:.2f}")
    
    greedy_selection = []
    greedy_weight = 0
    greedy_value = 0
    remaining_capacity = capacity
    
    print(f"\nGreedy execution (capacity = {capacity}):")
    for item in sorted_items:
        if item['weight'] <= remaining_capacity:
            greedy_selection.append(item['name'])
            greedy_weight += item['weight']
            greedy_value += item['value']
            remaining_capacity -= item['weight']
            print(f"  TAKE {item['name']}: weight={item['weight']}, value={item['value']}, remaining={remaining_capacity}")
        else:
            print(f"  SKIP {item['name']}: weight={item['weight']} > remaining={remaining_capacity}")
    
    print(f"\nGreedy result: {greedy_selection}, total value = {greedy_value}\n")
    
    # Step 3: Alternative Solution Feasibility
    print("=== Step 3: Alternative Solution Verification ===")
    alternative_selection = ['B', 'C']
    alternative_items = [item for item in items if item['name'] in alternative_selection]
    alternative_weight = sum(item['weight'] for item in alternative_items)
    alternative_value = sum(item['value'] for item in alternative_items)
    
    print(f"Alternative selection: {alternative_selection}")
    print(f"  Total weight: {alternative_weight}")
    print(f"  Total value: {alternative_value}")
    
    assert alternative_weight <= capacity, "Alternative exceeds capacity!"
    print(f"✓ Alternative weight {alternative_weight} ≤ capacity {capacity}\n")
    
    # Step 4: Strict Improvement Check
    print("=== Step 4: Improvement Verification ===")
    print(f"Greedy value: {greedy_value}")
    print(f"Alternative value: {alternative_value}")
    
    if alternative_value > greedy_value:
        improvement = alternative_value - greedy_value
        pct = (alternative_value / greedy_value - 1) * 100
        print(f"✓ Alternative is STRICTLY BETTER by {improvement} ({pct:.1f}% improvement)")
        print("\n=== COUNTEREXAMPLE VERIFIED ===")
    else:
        print("✗ Not a valid counterexample")
 
if __name__ == "__main__":
    verify_knapsack_counterexample()

When You Can't Find a Counterexample

What if you've tried multiple counterexample patterns and none of them work? This can indicate one of several situations:

When Counterexamples Prove Elusive

•The algorithm might be correct — Perhaps greedy actually works for this problem. The greedy choice property may hold. Time to attempt a proof.
•The counterexample requires rare structure — Some failures only occur with very specific input configurations. Try more extreme cases: very large/small values, many duplicates, special graph structures.
•The counterexample is large — Some greedy algorithms fail only for k ≥ 4 items or n ≥ 10 vertices. Try larger inputs systematically.
•You're attacking the wrong vulnerability — Revisit Step 2. What information does greedy ignore? Are you exploiting that correctly?
•Random testing can help — Generate many random inputs, run both greedy and optimal solver (brute-force for small inputs), and look for discrepancies.

The Bridge to Proofs:

Failing to find a counterexample after substantial effort is evidence (but not proof) that greedy might work. At this point, shift your approach:

State the greedy choice property precisely — What exactly is the claim that the first greedy choice is safe?
Attempt an exchange argument — If we had an optimal solution that didn't start with the greedy choice, can we exchange to get one that does without loss of quality?
Verify optimal substructure — After making the greedy choice, is the remaining problem a smaller instance of the same problem?

If you can establish these, the greedy algorithm is correct. If you find a gap in the proof logic, that gap often points directly to a counterexample structure.

The Duality Principle

random_counterexample_search.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
63
64
65
66
67
68
69
70
71
import random
from itertools import combinations
 
def greedy_knapsack(items, capacity):
    """Greedy by value/weight ratio."""
    sorted_items = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    total_weight = 0
    for weight, value in sorted_items:
        if total_weight + weight <= capacity:
            total_value += value
            total_weight += weight
    return total_value
 
def optimal_knapsack(items, capacity):
    """Brute-force optimal (exponential, for small inputs only)."""
    best = 0
    for r in range(len(items) + 1):
        for subset in combinations(items, r):
            total_weight = sum(item[0] for item in subset)
            total_value = sum(item[1] for item in subset)
            if total_weight <= capacity and total_value > best:
                best = total_value
    return best
 
def search_for_counterexamples(num_trials=10000, max_items=5, max_weight=20, max_value=100, max_capacity=50):
    """
    Randomly generate inputs and check if greedy ever fails.
    """
    counterexamples_found = []
    
    for trial in range(num_trials):
        # Generate random items
        n_items = random.randint(2, max_items)
        items = [(random.randint(1, max_weight), random.randint(1, max_value)) 
                 for _ in range(n_items)]
        capacity = random.randint(1, max_capacity)
        
        greedy_result = greedy_knapsack(items, capacity)
        optimal_result = optimal_knapsack(items, capacity)
        
        if greedy_result < optimal_result:
            counterexamples_found.append({
                'items': items,
                'capacity': capacity,
                'greedy': greedy_result,
                'optimal': optimal_result,
                'gap': optimal_result - greedy_result
            })
    
    print(f"Searched {num_trials} random inputs")
    print(f"Found {len(counterexamples_found)} counterexamples")
    
    if counterexamples_found:
        # Show the smallest counterexample
        smallest = min(counterexamples_found, key=lambda x: len(x['items']))
        print(f"\nSmallest counterexample:")
        print(f"  Items (weight, value): {smallest['items']}")
        print(f"  Capacity: {smallest['capacity']}")
        print(f"  Greedy value: {smallest['greedy']}")
        print(f"  Optimal value: {smallest['optimal']}")
        
        # Show the largest gap
        worst = max(counterexamples_found, key=lambda x: x['gap'])
        print(f"\nLargest gap counterexample:")
        print(f"  Items: {worst['items']}")
        print(f"  Capacity: {worst['capacity']}")
        print(f"  Greedy: {worst['greedy']}, Optimal: {worst['optimal']}, Gap: {worst['gap']}")
 
if __name__ == "__main__":
    search_for_counterexamples()

Counterexamples in Technical Interviews

Scenario: You're solving a problem and propose a greedy approach. The interviewer asks: "Are you sure that works?"

This is your cue to do one of two things:

Provide a convincing correctness argument (greedy choice property + optimal substructure)
Find a counterexample and pivot to a correct approach

Interview Best Practices

•Verbalize your process — 'Let me try to break my greedy with a small example...' shows methodical thinking.
•Start minimal — 'What if there are just 2 items?' Then expand: 'What about 3 items?'
•Identify the greedy criterion explicitly — 'My greedy picks by maximum profit. What if that conflicts with...'
•When you find a counterexample, explain why it works — 'This breaks because the greedy picks A, but A blocks access to B and C which are collectively better.'
•Pivot confidently — 'Since greedy doesn't work, this has overlapping subproblems, so let me try dynamic programming.'
•If greedy is correct, explain why — 'The greedy choice is safe because we can always exchange any optimal solution's first choice with ours without loss.'

The Interviewer's Perspective

Common Interview Problem Types Where Greedy Fails (and candidates often try it):

Problem	Common (Wrong) Greedy	Why It Fails	Correct Approach
Coin Change	Largest coin first	Non-canonical coins	DP
0/1 Knapsack	Best ratio first	Discrete choices	DP
Longest Increasing Subsequence	Greedy extend	Can't undo past choices	DP
Edit Distance	Greedy match	Needs optimal alignment	DP
Partition Equal Subset	Greedy fit	Subset sum is NP-hard	DP
Word Break	Greedy longest match	Can block valid breaks	DP/Backtracking

Knowing these patterns helps you avoid greedy traps and quickly pivot to correct approaches.

Advanced: Systematic Adversarial Input Generation

Technique 1: Boundary Value Analysis

Greedy algorithms often have decision boundaries. Construct inputs that sit exactly on these boundaries:

If greedy compares ratios, create items with equal ratios
If greedy uses thresholds, place values at exactly the threshold
If greedy has tie-breaking rules, create ties that exercise the tie-breaker

Technique 2: Extremal Inputs

Push parameters to extremes:

Single item — Does greedy work when there's only one choice?
Maximum capacity — What if capacity equals total item weight?
Zero capacity — Edge case for resource-constrained problems
All equal — All items have the same value/weight/priority
Sorted inputs — Already sorted ascending, descending, or by the greedy criterion
Anti-sorted — Sorted opposite to the greedy criterion

Technique 3: Parameterized Construction

Create a family of inputs controlled by a parameter k:

For k from 2 to 10:
  Create k small items that collectively beat one large item
  Run greedy and check if it picks the large item wrongly

This helps find the minimum k where greedy fails.

Technique 4: Inverse Engineering

Start with the solution and work backward:

Define an optimal solution S* that you know is correct
Identify what greedy would choose first instead of S*'s first element
Set parameters so that greedy's choice has slightly better local score
Verify that S* is globally better despite worse first choice

Example: For interval scheduling, if optimal selects intervals {A, B, C}:

Create a competing interval D that starts earliest (greedy criterion)
Make D overlap with all of A, B, C
Make A, B, C non-overlapping with each other
Greedy picks D (1 interval), optimal picks {A, B, C} (3 intervals)

Computational Adversarial Testing

Summary: Counterexample Construction

Constructing counterexamples is a fundamental skill that separates novice problem-solvers from experts. We've covered the complete methodology:

Key Takeaways

•Adopt the adversarial mindset — Think like an attacker trying to break the algorithm. You control the input.
•Follow the systematic 5-step process — Identify criterion, identify ignored information, create trap, create alternative, verify.
•Recognize common patterns — Blocker, capacity trap, delayed payoff, denomination mismatch, high-degree hub.
•Verify rigorously — Check constraints, trace execution, confirm feasibility, prove strict improvement.
•Know when to pivot — If counterexamples prove elusive, attempt a correctness proof instead.
•Practice in interviews — Articulating why greedy fails demonstrates deep algorithmic understanding.
•Use systematic generation — Boundary values, extremes, parameterized families, and inverse engineering.

Page Complete