Greedy Algorithm Counterexamples for Coding Interviews

Greedy solutions feel elegant—until they fail on a hidden edge case. Knowing when greedy works (and when it doesn't) is a fast way to impress interviewers and avoid wrong turns.

TL;DR

• Greedy picks the locally optimal choice hoping it leads to the global optimum; counterexamples reveal when that hope breaks.
• Interviews love greedy because it tests intuition and proof skills, not just coding speed.
• Steps: define the choice, test with counterexamples, attempt an exchange argument, and only then commit.
• Beginners misread the problem objective and skip the proof sketch.
• This guide gives visual counterexamples, a proof pattern, and practice tips.

Beginner-Friendly Explanation

A greedy algorithm makes an irreversible choice based on the current best-looking option. If that choice can always be swapped with an optimal solution without hurting it, greedy is valid.

Why Counterexamples Matter

• They expose incorrect heuristics before you code.
• They strengthen your explanation during a mock interview simulator session.
• They highlight when to pivot to DP or backtracking.

Step-by-Step Learning Guidance

1) State the Greedy Choice Clearly

Example: "Always pick the interval with the earliest finishing time."

2) Search for Counterexamples

• Change order, tie-breakers, or ratios to see if the rule breaks.
• Use small inputs (3–5 elements) to reason quickly.

3) Attempt an Exchange Argument

Show that if an optimal solution doesn't follow your greedy choice, swapping in your choice keeps or improves optimality.

4) Lock in or Pivot

If the exchange argument fails, switch to DP. LeetCopilot can surface hints about which subproblem structure to try next.

Visual Counterexamples to Memorize

Coin Change with Denominations [1, 3, 4]

Greedy (largest coin first) gives 6 = 4 + 1 + 1 (3 coins). Optimal is 3 + 3 (2 coins). The ratio heuristic fails.

Shortest Superstring with Overlaps

Picking the pair with the largest immediate overlap can block a better global merge. You need DP over subsets.

Activity Selection Variant with Weights

Earliest finish time fails when activities have values; you need DP or a different greedy proof.

These examples are small enough to rehearse before proposing greedy.

Practical Preparation Strategies

• Make a two-column sheet: left side = greedy rule, right side = smallest counterexample.
• Rehearse exchange arguments: Start with interval scheduling (works) vs. coin change (fails). For more interview prep guidance, see how to run mock coding interviews by yourself.
• Practice aloud: For more practice guidance, see how to practice LeetCode without memorizing solutions.
• Timebox: Spend 3–4 minutes testing greedy; if still unsure, pivot to a safer approach.

Common Mistakes to Avoid

Ignoring the Objective Function

Minimizing number of coins vs. total value vs. lexicographic order changes validity. Always restate the objective before committing.

Handwaving Proofs

Saying "it seems to work" isn't enough. Provide a swap argument or monotonicity reasoning.

Forgetting Tie-Breakers

If multiple choices look equally good, define deterministic tiebreaks or test both in your counterexamples.

Code Example: Valid Greedy (Interval Scheduling)

function maxNonOverlappingIntervals(intervals: Array<[number, number]>): number {
  intervals.sort((a, b) => a[1] - b[1]); // earliest finish first
  let count = 0;
  let end = -Infinity;

  for (const [start, finish] of intervals) {
    if (start >= end) {
      count++;
      end = finish;
    }
  }
  return count;
}

This works because choosing the earliest finish time leaves maximum room for future intervals—a clean exchange argument exists. For more interview prep guidance, see how to explain your thought process during coding interviews.

FAQ

How do I know if greedy will fail?
If you can't articulate a swap argument or find a monotonic property, test small counterexamples before coding.

What should I practice first?
Start with interval scheduling and Huffman coding (work), then coin change with tricky denominations (fails).

Is greedy required in interviews?
It's common as a first attempt. Interviewers appreciate when you quickly test validity and pivot if needed.

How do I present a failure?
Explain the counterexample you tried and propose the next pattern (often DP). That shows structured reasoning, not guesswork.

Conclusion

Knowing greedy counterexamples turns a risky guess into a confident proposal. Lead with the choice, test it, sketch the swap proof, and use tools like LeetCopilot for guided practice—you'll impress interviewers with speed and rigor.