Greedy Algorithms: How to Know When Greedy Works (With Proofs and Counterexamples)

Greedy problems are the most deceptive questions in a coding interview. The code is often under 15 lines, which makes them look easy, and a wrong greedy rule frequently passes the examples in the problem statement. The real skill is not writing greedy code; it is knowing whether your greedy rule is correct, and being able to say why in two or three sentences.

This guide gives you a repeatable process: a checklist for spotting greedy problems, a counterexample-hunting routine, the two proof templates that cover nearly every interview greedy, and full worked solutions for the classics.

What Makes a Greedy Algorithm Correct

A greedy algorithm builds a solution step by step, at each step picking the option that looks best right now, according to some rule. It is correct when two properties hold:

1. Greedy-choice property: there exists an optimal solution that includes the greedy choice. So committing to it never closes the door on optimality.
2. Optimal substructure: after making the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to it combined with the greedy choice is optimal overall.

DP problems also have optimal substructure. The difference is property 1: in DP, you do not know which choice is safe, so you try all of them. Greedy says "I can prove this one choice is always safe."

Signals that a problem might be greedy

• The input can be sorted by some key, and the answer is built by scanning once.
• The question asks for a maximum count of compatible things or a minimum number of resources (rooms, arrows, platforms, jumps).
• Constraints are large (n up to 10⁵ or 10⁶), ruling out O(n²) DP.
• Choices are independent of future choices in a way you can articulate ("the earliest finishing meeting is never worse to keep").

Hunting Counterexamples: The Two-Minute Test

Before proving anything, try to break your rule. Most wrong greedies die on inputs of size 2 or 3. My routine in mock interviews: list two or three plausible greedy rules, then for each, construct the smallest input where it might fail, focusing on ties, extremes (one huge item), and items that "block" others.

The coin change trap deserves a note for Indian readers: rupee denominations (1, 2, 5, 10, 20, 50, 100, 200, 500) form a canonical system where the greedy "largest note first" is optimal, which is why cashiers do it. The interview problem deliberately uses arbitrary coins to break that intuition; see LeetCode 322 Coin Change explained for the DP.

The Exchange Argument (and Greedy Stays Ahead)

Two proof templates cover nearly every greedy you will justify in an interview. You do not need formal notation; a crisp paragraph is enough.

Template 1: exchange argument

1. Let G be the greedy solution and O any optimal solution.
2. Find the first point where they differ. Greedy chose g, optimal chose o.
3. Swap o for g in O. Show the result O' is still valid (feasible).
4. Show O' is no worse than O. So O' is also optimal and agrees with G for one more step.
5. Repeat until O' equals G. Hence G is optimal.

Template 2: greedy stays ahead

Define a measure of progress (for example, "end time of the k-th chosen activity" or "farthest index reachable after k jumps"). Prove by induction that after every step, greedy's measure is at least as good as any other solution's. Then greedy cannot finish worse.

Template 3: structural bound

Show a lower bound that any solution must meet (for example, "we need at least as many rooms as the maximum number of overlapping meetings"), then show greedy achieves it. Meeting Rooms II and Minimum Arrows use this.

Activity Selection / Non-Overlapping Intervals (435)

Given intervals, choose the maximum number that do not overlap (equivalently, remove the minimum number so the rest do not overlap). Greedy rule: sort by end time; take each interval whose start is at or after the end of the last taken interval.

Proof (exchange): let a be the interval with the earliest end, and let O be an optimal set whose first interval (by end time) is o. Since a ends no later than o, replacing o with a cannot create an overlap with O's other intervals (they all start after o ends, so after a ends too). The new set has the same size, so it is optimal and contains a. Remove a and everything overlapping it, and the remaining problem is the same problem on a smaller set. Induction finishes the proof.

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int kept = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) {          // compatible: take it
            kept++;
            lastEnd = iv[1];
        }
    }
    return intervals.length - kept;      // removals
}

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return len(intervals) - kept

Dry run on [[1,2],[2,3],[3,4],[1,3]]: sorted by end → [1,2], [2,3], [1,3], [3,4]. Take [1,2] (lastEnd 2). Take [2,3] (2 ≥ 2, lastEnd 3). Skip [1,3] (1 < 3). Take [3,4]. Kept 3, removals 1. O(n log n) for sorting.

Same skeleton, different wording: Minimum Number of Arrows to Burst Balloons (452) (arrows = number of greedy picks with a strict > since touching balloons burst together), Maximum Length of Pair Chain (646), and the scheduling questions in the intervals interview problems guide. When the question is "minimum rooms" rather than "maximum activities", you need a heap or a sweep instead (see the heap guide).

Jump Game I and II: Farthest Reach

Jump Game (55): can you reach the end?

nums[i] is the maximum jump length from i. Track reach, the farthest index reachable so far. Scan left to right; if you ever stand at an index greater than reach, you are stuck.

bool canJump(vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;            // index i is unreachable
        reach = max(reach, i + nums[i]);
        if (reach >= (int)nums.size() - 1) return true;
    }
    return true;
}

Why it is correct: the set of reachable indices is always a prefix [0, reach], because if you can reach index j you can reach every index before it (jumps can be shorter than the maximum). So a single number describes the whole reachable set, and the scan updates it exactly. A DP that marks each reachable index is O(n²); this is O(n).

Jump Game II (45): minimum number of jumps

Think of it as BFS where level k is the range of indices reachable in exactly k jumps. Those ranges are contiguous, so you only need their boundaries: curEnd (end of the current level) and farthest (end of the next level).

def jump(nums):
    jumps = 0
    cur_end = 0          # last index reachable with `jumps` jumps
    farthest = 0
    for i in range(len(nums) - 1):          # no jump needed from the last index
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                    # finished scanning this level
            jumps += 1
            cur_end = farthest
            if cur_end >= len(nums) - 1:
                break
    return jumps

Dry run on [2, 3, 1, 1, 4]: i=0, farthest 2, i == curEnd 0 → jumps 1, curEnd 2. i=1, farthest 4. i=2, farthest 4, i == curEnd → jumps 2, curEnd 4 ≥ 4, stop. Answer 2 (0 → 1 → 4).

Proof (stays ahead): after k jumps, greedy's curEnd is the farthest index any sequence of k jumps can reach, by induction: any k+1-th jump starts from some index within the k-th level and greedy took the maximum over all of them. So greedy reaches the end with the fewest jumps.

Gas Station (134): Reset the Start When the Tank Goes Negative

n stations in a circle; gas[i] is fuel available at i, cost[i] is fuel to drive to i+1. Find the starting station that lets you complete the circuit, or −1. The answer is guaranteed unique if it exists.

public int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {          // cannot reach i+1 from `start`
            start = i + 1;       // no station in [start, i] can work either
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

Two facts make this O(n) greedy correct, and you should state both:

1. If the total gas is less than total cost, no start works. Obvious: you need at least as much fuel as you burn.
2. If starting at s you first run dry before reaching i+1, then no station k in (s, i] can be the start either. When you passed k coming from s, your tank was ≥ 0 (you had not run dry yet). Starting fresh at k means arriving at k with exactly 0, which is no better. So from k you would also run dry by i+1. That justifies skipping the whole block.

Finally, if total ≥ 0, the last chosen start works: the segment from start to the end has non-negative running sums, and the earlier part of the circle (which we reset over) has a total that, combined with the tail, is ≥ 0, so the tail's surplus covers the wrap-around.

Dry run: gas [1,2,3,4,5], cost [3,4,5,1,2]. Diffs: −2, −2, −2, 3, 3. i=0 tank −2 → start 1. i=1 tank −2 → start 2. i=2 tank −2 → start 3. i=3 tank 3. i=4 tank 6. Total 0 ≥ 0, answer 3.

Huffman Coding: Merge the Two Smallest

Given character frequencies, build a prefix-free binary code that minimises total encoded length (sum of frequency × code length). Huffman's algorithm: put all frequencies in a min-heap; repeatedly remove the two smallest, create a parent node with their sum, and insert it back. The tree you build defines the codes (left = 0, right = 1).

import heapq
from itertools import count

def huffman_codes(freq):
    tie = count()                          # tie-breaker so nodes are never compared
    heap = [(f, next(tie), ch) for ch, f in freq.items()]
    heapq.heapify(heap)
    if len(heap) == 1:                     # single symbol edge case
        return {heap[0][2]: "0"}
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tie), (a, b)))
    codes = {}

    def walk(node, prefix):
        if isinstance(node, tuple):
            walk(node[0], prefix + "0")
            walk(node[1], prefix + "1")
        else:
            codes[node] = prefix

    walk(heap[0][2], "")
    return codes

# huffman_codes({"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5})
# a gets a 1-bit code; e and f get the longest (4-bit) codes.

Why merging the two smallest is optimal (exchange): in an optimal tree, the two deepest leaves are siblings. If the two least frequent symbols x and y are not the deepest, swap them with the deepest pair; moving a less frequent symbol deeper and a more frequent one shallower can only reduce the total cost. So some optimal tree has x and y as sibling leaves at maximum depth. Merging them into one symbol of frequency f(x)+f(y) gives a smaller instance whose optimal tree extends to an optimal tree for the original. That is the greedy-choice property plus optimal substructure, exactly as defined above.

The interview disguise: Minimum Cost to Connect Sticks (1167). Merging two sticks costs their sum; minimise total cost. It is Huffman's total cost computation without the codes: O(n log n) with a heap. Same idea in Optimal Merge Pattern questions from Indian campus placements.

More Greedy Patterns Worth Knowing

Two-pass greedy: Candy (135)

Each child gets at least one candy; a child with a higher rating than a neighbour gets more than that neighbour. Pass left to right enforcing the left-neighbour rule, then right to left enforcing the right-neighbour rule with max. Each pass is locally greedy; together they satisfy both constraints with the minimum total.

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> c(n, 1);
    for (int i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--)
        if (ratings[i] > ratings[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
    return accumulate(c.begin(), c.end(), 0);
}

Sort + two pointers

• Assign Cookies (455): sort both; give each child the smallest cookie that satisfies them. Using a bigger cookie than needed never helps (exchange).
• Boats to Save People (881): sort; pair the heaviest with the lightest if they fit, otherwise the heaviest goes alone. The heaviest person must be in some boat; pairing them with the lightest is the least restrictive choice.

Last-occurrence greedy: Partition Labels (763)

Record each character's last index. Extend the current partition's end to the max last index of characters seen; when i reaches that end, cut. Each cut is as early as possible, which maximises the number of parts.

Greedy with a heap

When the best choice changes as you go, a heap supplies it: IPO (502), Course Schedule III (630: sort by deadline, keep a max-heap of durations, drop the longest when over time), Minimum Number of Refueling Stops (871). These are greedy algorithms whose "regret" step (undo the worst earlier choice) is what makes them correct.

Greedy on digits and strings

Remove K Digits (402) uses a monotonic stack: remove a digit whenever the next digit is smaller, because a smaller digit in a higher position always wins. Largest Number (179) sorts by the comparator a + b > b + a; proving that comparator is transitive is a nice exchange-argument exercise.

Greedy in graphs

Dijkstra (always finalise the closest unvisited vertex), Prim and Kruskal (always add the lightest safe edge) are greedy algorithms with famous proofs. Kruskal's cut-property proof is spelled out in the union-find guide.

Greedy vs Dynamic Programming: A Decision Table

Weighted Job Scheduling is the perfect contrast to activity selection: one extra attribute (profit) breaks the greedy-choice property, because a short early job might have tiny profit. The DP interview guide covers it.

How Greedy Problems Are Evaluated in Interviews

Because greedy code is short, interviewers judge you mostly on reasoning. A strong answer follows this shape:

1. State the rule precisely. "Sort by end time ascending; take an interval if it starts at or after the last taken end."
2. Name a rejected rule and its counterexample. "Sorting by start fails on [1,10], [2,3], [4,5]." This shows you checked.
3. Give a short justification. One paragraph of exchange or stays-ahead reasoning.
4. Code and dry run on the example plus one edge case (ties, single element, all overlapping).
5. Complexity: usually O(n log n) for the sort plus O(n) for the scan.

Common follow-ups: "What if intervals have weights?" (DP), "What if the stream is online?" (heap-based greedy with regret), "Prove the comparator is transitive" (Largest Number), "What if you can do at most K operations?" (heap). If you are asked "is this optimal?" and you are not sure, say so and propose a DP fallback. Interviewers respect calibrated confidence far more than a confident wrong greedy.

Common Greedy Mistakes

• Sorting by the wrong key (start instead of end, ratio instead of weight).
• Wrong tie-breaking. Queue Reconstruction by Height (406) needs height descending, then k ascending; flip the second key and it fails.
• Boundary conditions: >= vs > for touching intervals differs between Non-overlapping Intervals and Minimum Arrows.
• Comparator overflow in Java with a[1] - b[1] on large values. Use Integer.compare.
• Using greedy where DP is required because constraints were small enough for DP and you did not check.

Greedy Practice List with the Proof Idea

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.