Phase 6 — Greedy, Proofs & Mathematical Thinking

Target level: Medium → Hard Expected duration: 1.5 weeks (12-week track) / 2 weeks (6-month track) / 2.5 weeks (12-month track) Weekly cadence: ~7 greedy concepts plus 6 labs plus 25–40 problems applying them under the framework

Why Greedy Is The Single Most Dangerous Pattern Family In Coding Interviews

Greedy is the topic where the largest number of candidates fail confidently. Unlike dynamic programming, where the failure mode is “I cannot derive the recurrence” — a visible failure that the interviewer can help with — greedy’s failure mode is “I have a plausible algorithm, I have run it on the given example, it works, and I am wrong.” The candidate writes a clean function, the test cases pass, the complexity is excellent, and the algorithm is silently incorrect on the third hidden test. By the time the interviewer reveals the counterexample, the candidate has consumed 25 minutes building a wrong solution and has 10 minutes left to either patch it (impossible without re-deriving) or restart with DP (also impossible).

The empirical claim that drives this entire phase:

The hard part of greedy is not the algorithm. The hard part is the proof of correctness. Almost every wrong greedy solution is wrong because the candidate convinced themselves “this seems to work” without an exchange argument or invariant — and an interviewer who suspects the candidate is guessing will deliberately construct a counterexample. A candidate who can produce an exchange argument out loud, before the interviewer asks, is signalling “I know what I’m doing”; a candidate who can’t is signalling “I memorized this”.

Greedy is also the topic where the gap between a good engineer and a great one is widest in interview signal. Most candidates can write sort + scan + counter. Very few can articulate why the sort criterion is correct. The ability to say, in 60 seconds, “Suppose for contradiction the optimal solution uses a different first choice; I can exchange it with my greedy choice without making the solution worse, therefore my greedy is also optimal” — that one paragraph is the entire difference between an L4 hire and an L5 hire on greedy questions.

This phase is built around one teaching device that we will use on every single problem from start to finish: the proof comes before the code. Every lab in this phase requires you to write the correctness argument — exchange argument, invariant, or monovariant — before you write the implementation. The implementation is mechanical once the proof is solid; the proof is the whole skill.

After this phase, you can recognize when a problem is amenable to greedy in <2 minutes, produce an exchange argument out loud in <90 seconds, write the algorithm in <5 minutes, and — crucially — identify when a problem looks greedy but is not, falling back to DP from Phase 5 without panic.

What You Will Be Able To Do After This Phase

  • Recognize greedy candidates in <2 minutes by spotting the greedy choice property signal: “the locally optimal choice cannot hurt the global optimum.”
  • Distinguish greedy-applicable problems from DP-required problems on first read, using the Greedy-vs-DP flowchart.
  • Produce an exchange argument for any greedy you propose, in the canonical four-step form (assume optimal differs, locate first divergence, exchange, prove no-worse).
  • Cite the cut property for MST correctness and explain why both Kruskal and Prim are correct under it.
  • Use loop invariants to scaffold proofs of greedy algorithms whose correctness is not obvious from a single exchange.
  • Use monovariants (strictly-decreasing or strictly-increasing quantities) to prove termination and correctness of iterative greedy algorithms.
  • Apply amortized analysis (potential method, accounting method, aggregate analysis) to bound the cost of greedy data-structure operations.
  • Identify counterexamples to plausible-looking greedy heuristics, including the canonical “0/1 knapsack ≠ fractional knapsack” trap.
  • Implement and prove correct: interval scheduling, jump game II, task scheduler, gas station, Huffman coding, and the greedy-vs-DP comparison on coin change.
  • Articulate the failure modes of greedy unprompted: missing counterexample, “feels right” without proof, confusing local optimum with global optimum.

How To Read This Phase

Read this README in two passes. Pass 1: linear, end-to-end, building the mental discipline that “I will not ship a greedy solution without an exchange argument.” Do this in one sitting. Pass 2: as you work the labs, refer back to specific concept entries when stuck on a proof.

Each concept entry has a fixed shape:

  1. Precise Definition — what the concept means, mathematically.
  2. When Applicable — the problem signal that should fire this concept.
  3. Worked Example — the concept applied to a canonical problem, end-to-end.
  4. Common Misuse — the concrete failure mode this concept guards against.

The phase ends with a Greedy-vs-DP flowchart, a Common Greedy Bugs catalog, a Mastery Checklist, and Exit Criteria.

Inline Concept Reference

1. Greedy Choice Property

Precise Definition

A problem has the greedy choice property if there exists an ordering of the input such that, after making the locally optimal choice (the “greedy choice”) at each step, the result is a globally optimal solution. Formally: at every step i, there is a choice c_i such that some globally optimal solution to the original problem extends c_1, c_2, …, c_i. Equivalently, after the greedy choice the remaining problem is a smaller instance of the same problem, and combining the greedy choice with any optimal solution to the residual problem yields an optimal solution to the original.

This is the formal cousin of optimal substructure (which DP also requires) plus the additional claim that a single locally optimal choice — not a search over choices — suffices at each step.

When Applicable

The greedy choice property holds when:

  • The problem can be solved by a sequence of irreversible decisions.
  • At each step, there is a most attractive choice by some natural metric (earliest deadline, smallest weight, largest ratio, latest start time).
  • An exchange argument or cut property can be invoked to prove that the most-attractive choice is never the wrong one.

The greedy choice property does not hold when:

  • The right choice at step i depends on choices made at step i+1, i+2, … (i.e., you must “look ahead” to decide). This is the DP regime.
  • There are multiple incomparable “locally optimal” candidates and the wrong one creates suboptimal residual problems.

Worked Example: Activity Selection

Given n activities with start and end times, pick the maximum number of non-overlapping activities.

The greedy choice: pick the activity with the earliest end time among those still compatible with the previous picks. This satisfies the greedy choice property because: any optimal solution either contains the earliest-ending activity, or — if it doesn’t — we can swap its first picked activity for the earliest-ending one without overlap and without changing the count, producing a new optimal solution that does. (See Lab 01 — Interval Scheduling for the full exchange argument.)

Common Misuse

The most common error is to assume the greedy choice property without proving it, on the basis that “earliest deadline first feels intuitive”. Counter-examples are everywhere; for example, “earliest start time” also feels intuitive but is wrong (consider one activity from 1 to 100 versus dozens of short activities from 2 to 3, 3 to 4, …). The discipline: every greedy claim must be paired with a proof.

2. The Exchange Argument — The Canonical Greedy Proof Technique

Precise Definition

An exchange argument proves that a greedy solution G is optimal by showing that any other solution O can be transformed into G without increasing cost (or decreasing value) via a sequence of exchanges. Each exchange replaces an element of O with the corresponding element of G and proves the swap is non-worsening. After all exchanges, O has been transformed into G, so G is at least as good as O. Since O was arbitrary, G is at least as good as any solution — i.e., G is optimal.

Step-By-Step Recipe

The recipe is rigid. Memorize it. Use it on every greedy proof.

  1. Let G be the greedy solution. Define it precisely (e.g., “the activities chosen by earliest-end-time-first”).
  2. Let O be an arbitrary optimal solution. Assume O ≠ G (otherwise we’re done).
  3. Locate the first index where they differ. Let i be the smallest index such that O[i] ≠ G[i]. By construction, G[0..i-1] = O[0..i-1].
  4. Perform the exchange. Replace O[i] with G[i], producing a new solution O'.
  5. Prove O' is feasible (still satisfies all constraints).
  6. Prove O' is no worse than O (same objective value, or no-worse if it’s a max/min).
  7. Repeat. O' agrees with G on more positions than O did. Iterate; after finitely many exchanges, O has been transformed into G. Therefore G is optimal.

Worked Example: Activity Selection

Greedy G = activities sorted by end time, picked greedily. Suppose O ≠ G is optimal. Let i be the first divergence. By the greedy rule, G[i] has the earliest end time among activities compatible with G[0..i-1] = O[0..i-1]. So G[i].end ≤ O[i].end. Replace O[i] with G[i]: feasibility holds because G[i] ends no later than O[i], so all subsequent activities in O[i+1..], which all start after O[i].end, also start after G[i].end. The objective (count of activities) is unchanged. Repeat until O = G. QED.

Common Misuse

  • Skipping step 5 (feasibility). Many “exchanges” produce an infeasible solution, invalidating the proof.
  • Skipping step 6 (no-worse-than). The exchange must be non-worsening, not merely “different”.
  • Stopping after one exchange. A single exchange shows G[0] = O'[0]; you must iterate.
  • Picking the wrong index to exchange. Exchanging at the last difference rather than the first often fails because residual structure differs.
  • Treating the exchange as a swap of types rather than concrete elements. Exchange a specific element of O with a specific element of G, not “exchange the early-ending one with the late-ending one”.

3. The Cut Property (MST Correctness)

Precise Definition

For a connected, weighted, undirected graph G = (V, E), the cut property states: for any cut (S, V\S) (a partition of vertices into two non-empty sets), the minimum-weight edge crossing the cut belongs to some minimum spanning tree of G. (If the minimum is unique, it belongs to every MST; if tied, at least one MST contains it.)

When Applicable

The cut property is the correctness theorem for greedy MST algorithms — Kruskal’s, Prim’s, Borůvka’s. It also generalizes to matroid theory: the greedy algorithm is correct on a structure iff the structure is a matroid.

Worked Example: Kruskal’s Algorithm

Kruskal sorts edges ascending by weight and adds each edge that doesn’t create a cycle. Correctness via the cut property: when Kruskal adds edge (u, v), the union-find structure tells us u and v are in different components — call them S and V\S (where S is u’s component and everything else, including v’s component, is V\S). Edge (u, v) crosses this cut. Because Kruskal scans edges in ascending order and (u, v) is the first edge (by weight) that crosses this cut without forming a cycle, it is the minimum-weight edge crossing the cut. By the cut property, (u, v) belongs to some MST. By induction, the set of edges Kruskal has added so far is a subset of some MST. After processing all edges, Kruskal’s set of edges is exactly an MST.

(Phase 4’s MST labs cover this in algorithmic detail; this phase’s job is the proof.)

Common Misuse

  • Applying the cut property to directed graphs. It only applies to undirected MST.
  • Assuming the MST is unique. Tie-breaking matters; multiple MSTs may exist.
  • Forgetting connectedness. On a disconnected graph, you compute a minimum spanning forest, not an MST.

4. Loop Invariants (Proof Scaffolding)

Precise Definition

A loop invariant is a property P(state) that holds before the loop, after every iteration, and after the loop terminates. To prove a loop is correct, show:

  1. Initialization — P holds before the first iteration (i.e., on the initial state).
  2. Maintenance — if P holds at the start of iteration k, then P holds at the end of iteration k.
  3. Termination — when the loop exits, P (combined with the exit condition) implies the desired postcondition.

Loop invariants are the workhorse of proving greedy algorithms whose correctness isn’t a single one-shot exchange argument — they’re scaffolding for “this thing stays true throughout the run”.

Worked Example: Gas Station (LC 134)

Greedy: scan stations once, maintain tank = 0 and start = 0. At station i, tank += gas[i] - cost[i]. If tank < 0, set start = i + 1 and reset tank = 0. Final answer: start if total gas ≥ total cost, else -1.

Loop invariant: at the end of iteration i, tank equals the net fuel accumulated from start to i, and no station in [start, i] (other than possibly start) is a valid starting point.

(Full proof in Lab 04 — Gas Station.)

Common Misuse

  • Inventing an invariant after the fact that conveniently equals “the answer is correct”. The invariant must be precisely statable independent of the conclusion.
  • Failing to prove maintenance — usually because the invariant is too weak (doesn’t survive one iteration) or too strong (false at initialization).
  • Skipping termination — the invariant might hold every iteration but the loop might not terminate at all, or might terminate in a state that doesn’t imply the postcondition.

5. Monovariants (Termination Arguments)

Precise Definition

A monovariant is a quantity that strictly increases (or strictly decreases) with every iteration of an algorithm and is bounded below (or above) by a known value. The existence of a monovariant proves termination: a strictly decreasing integer-valued quantity bounded below by 0 cannot decrease more than its initial value, so the loop runs at most that many iterations.

In greedy proofs, monovariants are also used to prove progress: each iteration makes irreversible progress toward the goal, so we never need to undo a choice.

Worked Example: Jump Game II (LC 45)

Greedy with two pointers: current_end and farthest. Scan; for each index, update farthest = max(farthest, i + nums[i]). When i == current_end, jump: jumps += 1, current_end = farthest.

Monovariant: farthest is non-decreasing across iterations; in fact farthest ≥ i + 1 for all i (otherwise we’d be stuck at an unreachable position, which is impossible if a solution exists). The monovariant guarantees we never need to backtrack — every position contributes to extending farthest, and current_end only ever moves forward.

(Full proof in Lab 02 — Jump Game II.)

Common Misuse

  • Confusing “increasing” with “non-decreasing”. A non-decreasing monovariant doesn’t prove termination — the algorithm might loop indefinitely with the quantity stuck. Use strictly increasing/decreasing.
  • Using a real-valued monovariant without an explicit lower bound on the rate of change. Real values can decrease toward an infimum without ever reaching it (Zeno’s paradox in algorithm form).
  • Treating monovariant as a correctness proof when it’s only a termination proof. Termination + invariant gives correctness; one of them alone does not.

6. Amortized Analysis

Amortized analysis bounds the cost of a sequence of operations by an average per-operation cost, even when individual operations may be expensive. It is essential for proving the cost of greedy data-structure operations — union-find with path compression, dynamic arrays, splay trees — and shows up in Phase 3 and Phase 7. We cover the three classical methods here.

6a. Aggregate Analysis

Bound the total cost of n operations by some function T(n), then divide: amortized cost per operation is T(n) / n. Simple to apply, hardest to derive a tight T(n) for.

Example. A dynamic array (Python list, Java ArrayList) doubles its capacity when full. n push operations cost: n for the actual writes, plus 1 + 2 + 4 + … + n/2 ≤ n for the resizes, total ≤ 2n. Amortized cost per push: 2n / n = O(1).

6b. The Accounting Method

Charge each operation a fixed amount (the “amortized cost”) which may exceed its actual cost. The excess is stored as “credit” on data-structure elements. Expensive operations pay using accumulated credits, never going into debt. If you can maintain “credits ≥ 0” as an invariant, the amortized cost is a valid upper bound.

Example. Dynamic array push: charge 3 per push. Actual cost is 1 for the write; 2 is stored as credit on the just-written element. When the array doubles, each element being moved already has 2 credits on it — exactly enough to pay for the move and the copy of one new element from the old half. Credits never go negative; amortized cost per push is O(1).

6c. The Potential Method

Define a potential function Φ(D) over data-structure states D, with Φ(D₀) = 0 initially and Φ(D) ≥ 0 always. The amortized cost of an operation is actual_cost + ΔΦ. Total amortized cost over n operations is Σ actual_cost + Φ(D_n) - Φ(D₀) ≥ Σ actual_cost, so it’s a valid upper bound.

Example. Dynamic array: let Φ = 2 · size − capacity. After a doubling, Φ = 0. Each push that doesn’t trigger doubling: actual cost 1, ΔΦ = +2, amortized 3. Doubling push: actual cost size + 1, ΔΦ = 2 − size, amortized 3. Constant O(1) amortized per push.

Common Misuse

  • Conflating amortized with average-case. Amortized is a worst-case bound on a sequence of operations; average-case is over a probability distribution on inputs. They are not the same.
  • Applying amortized bounds to a single operation. A single resize is O(n); only the average over a sequence is O(1).
  • Claiming credits go negative in the accounting method — invalidates the bound. Always verify the invariant.
  • Using a potential function that can become negative — invalidates the bound; Φ ≥ 0 is required.

7. When Greedy FAILS (Counterexamples)

The skill of greedy is not just knowing when it works but recognizing when it doesn’t before you commit. Memorize these traps.

7a. 0/1 Knapsack ≠ Fractional Knapsack

Fractional knapsack (you can take any fraction of an item): greedy by value-to-weight ratio is optimal. Sort items by v_i / w_i descending; take items in order, taking a fraction of the last item if needed.

0/1 knapsack (each item is take-or-skip): greedy by ratio is not optimal. Counterexample:

ItemWeightValueRatio
A11.51.5
B221.0
C221.0

Capacity = 3. Greedy by ratio takes A (capacity left 2), then B (capacity left 0), total 3.5. Optimum is B + C = 4.

The trap: ratio-greedy is correct under fractional flexibility, fails under integrality. The 0/1 version requires DP — see Phase 5 Lab 03.

7b. Coin Change With Arbitrary Denominations

For US coins {1, 5, 10, 25}, greedy (largest first) is optimal. For arbitrary denominations like {1, 3, 4} with target 6, greedy gives 4 + 1 + 1 = 3 coins; optimum is 3 + 3 = 2 coins. Greedy fails. Fall back to DP — see Lab 06 — Greedy vs DP for the canonical counterexample analysis.

7c. Scheduling With Weights

Interval scheduling (unweighted): greedy by earliest end time is optimal. Weighted interval scheduling (each interval has a weight, maximize total weight of non-overlapping picks): greedy fails. DP with binary-search predecessor pointer is correct, O(N log N).

7d. “Greedy By Farthest Reach” In Reachability

Some problems look like jump game but are not: e.g., on a weighted graph, “earliest arrival” by greedy farthest-reach is not Dijkstra; it requires the priority-queue refinement.

Common Misuse

  • Trusting “looks like jump game” reasoning. Always verify the greedy choice property formally. The signal is “I have an exchange argument” not “the example worked”.
  • Failing the cross-test. Try N=2 and N=3 by hand. Try a hostile counterexample. Try the input where all elements are equal, all are distinct, all are decreasing.
  • Forgetting the DP fallback. Many problems are “greedy if X, DP otherwise.” Know which side you are on before coding.

Greedy-Vs-DP Decision Flowchart

When a problem looks optimization-flavored, this flowchart determines whether to attempt greedy or jump straight to DP.

START → Is the problem an optimization (max / min) or counting?
        │
        ├── No (search / decision / construction) → Greedy candidate; check exchange argument.
        │
        └── Yes
            │
            ├── Can I sort the input by a single criterion (deadline, weight, ratio)
            │   such that processing in that order has the greedy choice property?
            │   │
            │   ├── Yes — and I can write a 4-step exchange argument in <90s →
            │   │   GREEDY. Code in <5 minutes.
            │   │
            │   └── No / not sure →
            │       Does the optimal answer at step i depend on choices at i+1, i+2, …?
            │       │
            │       ├── Yes → DP. State = (position, accumulated state needed for future).
            │       │   See Phase 5.
            │       │
            │       └── No / unclear → Try greedy with a small N=3, N=4 stress-test against
            │                          brute force. If matches → write proof attempt.
            │                          If diverges → DP.
            │
            └── Try the canonical counterexamples for this problem class:
                - Fractional vs 0/1 (knapsack)
                - Sorted vs arbitrary (coin change)
                - Unweighted vs weighted (scheduling)
                If any counterexample defeats your greedy → DP.

The flowchart’s discipline: never commit to greedy without an exchange argument. The 90-second time-box for the proof attempt is exactly the safety check that prevents the failure mode of confidently submitting wrong greedy code.

Common Greedy Bugs

A taxonomy. Each one shows up in at least 30% of submitted greedy solutions in mock interviews.

  1. Claiming greedy without proof. “I’ll sort by end time and pick” with no exchange argument. The interviewer asks “why?” and the candidate either restates the algorithm or stalls. Fix: practice the 4-step exchange recipe so it comes out automatically when you propose the algorithm.
  2. Wrong sort key. Sorting by start time when end time is correct (interval scheduling); sorting by weight when ratio is correct (fractional knapsack). Fix: before coding, do an exchange argument with each candidate sort key on a hand-crafted small example. The wrong key fails the exchange step quickly.
  3. Ignoring counterexamples. “My algorithm passes the examples, ship it.” Fix: always run the algorithm against brute force on N=2, N=3, N=4 random inputs before committing.
  4. Assuming local optimum = global optimum without justification. “At each step pick the smallest” works for some problems and fails for others. Fix: the greedy choice property is not free; it must be proven for every problem.
  5. Confusing fractional and integer regimes. Ratio-greedy on 0/1 knapsack; “take half of this” interpretation in problems where items are atomic. Fix: read the integrality constraint before coding.
  6. Off-by-one in “earliest end time” when ties exist. Ties must be broken consistently — typically by start time ascending — and the proof must handle ties. Fix: state the tie-breaker explicitly and verify the exchange argument handles it.
  7. Greedy with backtracking masquerading as greedy. Some “greedy” solutions secretly maintain a stack and pop on conflict (e.g., remove-k-digits LC 402, candy distribution LC 135). The pure greedy claim doesn’t apply; the algorithm is greedy plus an undo step. Fix: if your algorithm has an if conflict: undo, it’s not pure greedy; the proof must cover the undo logic.
  8. Mixing up the proof with the algorithm. “Earliest deadline first works because earliest deadline first is the best choice” is circular. Fix: the proof must reference an exchange or invariant or cut, not restate the algorithm.
  9. Not handling the empty / size-1 case in scan-based greedy. Fix: explicit guard at the start.
  10. Using a heap when sorting suffices (or vice versa). Heap is for online greedy where future inputs aren’t yet visible (e.g., merge K sorted lists, scheduling with deadlines streaming in). Sort is for offline where all inputs are known. Fix: ask “is the input streamed or batched?” up front.

Mastery Checklist

Before exiting this phase, verify all of these:

  • You can recognize a greedy candidate within 2 minutes by spotting the greedy choice property signal.
  • You can produce a 4-step exchange argument for any greedy claim within 90 seconds, out loud, without writing code first.
  • You can cite the cut property and apply it to prove Kruskal’s / Prim’s correctness from scratch.
  • You can articulate the difference between an invariant, a monovariant, and an exchange argument — and pick the right tool for a given proof.
  • You can perform aggregate, accounting, and potential-method amortized analyses on a dynamic-array example, in <5 minutes total.
  • You can name and articulate three canonical greedy counterexamples (0/1 vs fractional knapsack; coin change {1,3,4}; weighted interval scheduling).
  • You can implement interval scheduling, jump game II, task scheduler, gas station, and Huffman coding with full proofs in <90 minutes total.
  • You can articulate the greedy-vs-DP decision in <30 seconds for any optimization problem.
  • You catch yourself before committing to a greedy without an exchange argument — every time.

Exit Criteria

You may move to Phase 7 (Competitive Programming Acceleration) when all of the following are true:

  1. You have completed all six labs in this phase, with each lab’s mastery criteria checked off.
  2. You have solved at least 25 unaided greedy problems from LeetCode (mix of Medium and Hard) and reviewed each via REVIEW_TEMPLATE.md. On at least 20 of them, you wrote the exchange argument or invariant in the review before peeking at any solution.
  3. Your unaided success rate on Medium-Hard greedy problems is ≥ 65%.
  4. In a mock interview (phase-11-mock-interviews/), you correctly identify greedy-applicability within 2 minutes for at least 7 of 10 greedy-flavored problems and produce an exchange argument within 90 seconds for at least 6 of 10. You correctly reject greedy in favor of DP on at least 2 of the 10, citing a counterexample.
  5. You have never in this phase shipped a greedy solution without a written proof. This is the single discipline of Phase 6, and skipping it is a phase-failure.

If any of these fails, do another 15–20 greedy problems before moving on. Skipping this gate produces engineers who pattern-match “looks like greedy” and ship wrong code under deadline pressure — exactly the failure mode that gets candidates rejected at staff level.

Labs

Hands-on practice. Each lab follows the strict 22-section format. Every lab’s Correctness Argument section contains an explicit exchange argument or invariant + monovariant proof. This is the whole point of Phase 6.

  1. Lab 01 — Interval Scheduling (Activity Selection) — canonical exchange argument
  2. Lab 02 — Jump Game II — greedy reach + monovariant
  3. Lab 03 — Task Scheduler With Cooldown — greedy + math formula
  4. Lab 04 — Gas Station — greedy + invariant proof
  5. Lab 05 — Huffman Coding — greedy via heap + exchange-argument optimality
  6. Lab 06 — Greedy Vs DP (Coin Change Counterexample) — when greedy fails and DP is required

← Phase 5: Dynamic Programming · Phase 7: Competitive Programming → · Back to Top