Greedy Algorithm Interview Questions: Prove It Works

The thing that separates a passing greedy answer from a failing one is not the code. It is whether you can say, out loud, why the locally best choice adds up to the globally best answer. Most candidates we run through mock interviews jump straight to "I'll just sort and take the biggest each time," then freeze when the interviewer asks "how do you know that's optimal?" This article gives you the two proof techniques that cover almost every greedy interview problem, the fast way to recognize when greedy breaks, and worked examples using real problems.

A greedy algorithm has a simple shape. Select a candidate greedily according to some heuristic, and add it to your current solution if doing so doesn't corrupt feasibility, then repeat if not finished. The danger is also simple: a greedy algorithm without a correctness proof is a guess that looks like an algorithm. It will compile, pass the example the problem hands you, and break on the hidden test. Interviewers know this, which is why the proof is the real question.

Why interviewers push on the proof

When a problem has a clean greedy solution, the coding is often five lines. That leaves the interviewer nothing to evaluate except your reasoning. So they probe it. Expect "why does picking the earliest-ending interval work?" or "what if I gave you this input instead?" The subtext is that they want to see you distinguish a provable greedy from wishful thinking.

Here is the mental model to lead with. A greedy approach is safe only when the problem has two properties: the greedy choice property, that a globally optimal solution can be arrived at by making a series of locally optimal choices, and optimal substructure. A correctness proof of a greedy algorithm will in general rely on the optimal substructure and greedy choice property. If you cannot argue both in about ninety seconds, that is your signal to reach for dynamic programming instead. Two proof techniques cover almost every greedy problem in the textbooks, both can be sketched out loud in under ninety seconds, and if neither applies in that time, the problem is dynamic programming.

Technique 1: the exchange argument

This is the workhorse. The idea: take any optimal solution and show you can morph it, one swap at a time, into the greedy solution without ever making it worse. The idea of a greedy exchange proof is to morph a solution produced by any other algorithm into the solution produced by your greedy algorithm in a way that doesn't worsen the solution's quality. This shows that any other solution is no better than the greedy solution, which proves that greedy does in fact return the optimal solution.

The structure is almost mechanical. Assume there exists an optimal solution different from the greedy solution, consider the first point where the optimal and greedy solutions differ, prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the optimal solution, and conclude by induction that the greedy solution is optimal.

Worked example: Minimum Number of Arrows to Burst Balloons. You get intervals [xstart, xend] and want the fewest vertical arrows to pop every balloon. The greedy: sort by end coordinate, shoot an arrow at the end of the first balloon, skip every balloon that interval covers, repeat. This is activity selection in disguise, and it is the canonical exchange-argument problem. To prove that this algorithm gives us a maximal conflict-free schedule, we use an exchange argument; we are not claiming that the greedy schedule is the only one, there could be others. To say it in the room: suppose an optimal arrow placement differs from greedy at the first arrow. Greedy placed its arrow at the earliest end point. Slide the optimal solution's first arrow to that same point. Every balloon the optimal arrow popped started no later than this end point, so the moved arrow still pops them all. The solution is no worse, and now it agrees with greedy one step further. Induct.

Worked example: Maximize Sum Of Array After K Negations. You flip the sign of an element exactly k times and want the maximum sum. Greedy: always flip the current smallest value. The exchange argument is quick. If an optimal solution ever flipped a larger number while leaving a smaller (more negative) one unflipped, swap which one you flip; the sum does not decrease. The one subtlety worth volunteering before the interviewer asks: after you have flipped every negative, leftover flips should all land on the single smallest absolute value, because flipping it twice is a no-op. That edge case is where candidates lose the point.

When you write up the proof, mind the two traps the Cornell notes flag. Be careful about proofs by contradiction that start by assuming greedy differs from optimal, and you need to argue why the two elements you're swapping even exist out of order.

Technique 2: greedy stays ahead

The exchange argument transforms optimal into greedy. "Greedy stays ahead" does the opposite: it shows greedy is never behind in the first place. This style of proof works by showing that, according to some measure, the greedy algorithm always is at least as far ahead as the optimal solution during each iteration, and once you have established this you can use it to show the greedy algorithm must be optimal.

It shines when optimal solutions can have different sizes. These arguments are useful when optimal solutions might have different sizes, since you can use the fact that greedy stays ahead to explain why your solution must be no bigger or no smaller than the optimal.

Worked example: Partition Array Into Three Parts With Equal Sum. You want to know if an array splits into three contiguous parts of equal sum. Compute the total; if it is not divisible by three, return false. Otherwise scan left to right with a running sum and close off a part the instant you hit total/3. The staying-ahead flavor: the greedy cut point is the earliest index that reaches the target. Any valid partition's first cut sits at or after greedy's, which leaves at least as much room for the remaining two parts. Greedy never paints itself into a corner. This is a prefix sum problem at heart, and naming that pattern shows range.

Worked example: Longest Palindrome. Count each character; take every even count in full and add one for a single odd count in the middle. The measure that stays ahead is simply pairs used: greedy uses every available pair, and no arrangement can use more pairs than exist, so no palindrome can be longer. It is a counting argument that fits the same frame. See more like it under string interview questions.

Spotting when greedy is wrong

The expensive mistake is confidently coding a greedy that fails hidden tests. Two habits prevent it.

First, try to break your own choice with a tiny counterexample before you commit. The classic warning is the knapsack family. In the fractional knapsack problem one is given a list of items with weights and values, and greedy by value-to-weight ratio works there, but the same ratio greedy fails for 0/1 knapsack. If the problem forbids splitting an item, greedy is probably dead and DP is the answer.

Second, know that there is a precise theory of when greedy is guaranteed to work: matroids. For every weighted matroid, the Greedy algorithm returns an optimal solution. You will not prove matroid axioms in a 45-minute interview, but the one-liner is worth having: greedy-by-largest-weight is provably optimal exactly when the feasible sets form a matroid (Kruskal's MST is the textbook case), and outside that structure you owe a problem-specific proof. For the hereditary family of independent sets in graphs this greedy fails to find a maximum independent set, for example a star where the middle vertex has slightly higher cost, but there are hereditary families for which greedy produces the optimal solution regardless of the cost function, known as matroids.

Problems that look greedy but hide a twist show up often. Minimum Cost to Make Array Equalindromic rewards knowing the sum of absolute differences is minimized at the median, then handling the palindrome constraint on top. Construct String With Repeat Limit is greedy plus a heap: always place the largest allowed character, drop to the next when you hit the repeat limit. Previous Permutation With One Swap and Lexicographically Smallest String After Operations With Constraint both reward a greedy scan from the correct end with a careful tie-break. In each case the code is short and the proof is the interview.

How to practice this

Do not grind twenty greedy problems for speed. Pick five, and for each one write two or three sentences of justification in plain English before you touch code. Then force the question "what input breaks this?" If you cannot answer in a minute, you have found a problem that is secretly DP. We built the greedy question set and AI mock interviews around exactly this gap: the follow-up "prove it" is where real interviews are won and lost, so rehearse saying the proof out loud, not just passing the samples.

FAQ

How do I quickly decide if a problem is greedy or dynamic programming?

Try to state the greedy choice and its one-line justification. If you can argue that a locally best pick is always safe (via exchange or staying-ahead) in about a minute, go greedy. If every choice seems to depend on future choices and you keep needing to "look ahead," that coupling is the signature of DP.

Do I actually have to prove correctness in an interview, or just mention it?

You rarely write a formal proof, but you must sketch the argument. One or two sentences naming the exchange or staying-ahead idea is usually enough, and it is often the deciding signal. It's usually much easier to prove feasibility than optimality, and interviewers routinely hand-wave through it, but when writing up a formal proof you shouldn't skip the step.

What is the single most common greedy mistake?

Confusing "passes the given example" with "correct." A heuristic that feels right is not a proof. Build one small adversarial input before coding; if it breaks your greedy, you just saved yourself a failed round.

Is sorting always part of a greedy solution?

Often, but not always. Interval and scheduling problems usually sort first (by end time for Burst Balloons), which makes sorting worth reviewing alongside greedy. Counting-based greedies like Longest Palindrome need only a frequency map, and heap-driven ones like Construct String With Repeat Limit sort lazily as they go.

Which greedy problems should a beginner start with?

Start with the junior-tagged ones: Longest Palindrome, Maximize Sum Of Array After K Negations, and Partition Array Into Three Parts With Equal Sum. Each has a short proof you can rehearse, then step up to interval problems like Minimum Number of Arrows to Burst Balloons.