Greedy

Greedy algorithms are the easiest to write and the hardest to justify. The code is usually a single loop with one comparison in it; the difficulty is entirely in knowing whether that loop is right.

That imbalance is the whole subject. Anyone can propose a greedy rule. What separates a correct solution from a plausible one is being able to say, in a sentence, why the choice you just committed to can never turn out to be wrong.

The shape#

At each step, take the option that looks best right now, and never reconsider it. There is no backtracking, no table, and no memory of alternatives — which is why greedy solutions are typically O(n) or O(n log n) with O(1) space.

Best Time to Buy and Sell Stock is the cleanest example on the list. You are choosing a pair of days out of n, which sounds like O(n²), and it is not.

Watch what is carried between steps: two numbers, and nothing else. No day is ever revisited, and the pairs that were rejected are never stored — they are simply gone.

min_so_far = infinity
best = 0

for price in prices:
    if price < min_so_far:
        min_so_far = price            // a cheaper day to buy on
    else:
        best = max(best, price - min_so_far)

return best

Why this one is safe#

Here is the justification, and the shape of it is worth copying:

Fix a selling day. The best profit achievable on that day is the price minus the cheapest price before it — nothing else can do better, because every valid buy day is behind it. The scan computes exactly that for every day, and the answer is the largest of them.

That argument does not appeal to intuition or to the examples passing. It converts the question “is my greedy rule right?” into “have I enumerated every case?” — and here the cases are the n possible selling days, each handled once.

When greedy is correct#

Formally, two properties have to hold:

• The greedy choice property. There exists an optimal solution that includes the choice greedy makes first. Not “greedy’s choice is obviously good” — some optimal solution contains it.
• Optimal substructure. After making that choice, what remains is a smaller instance of the same problem, and solving it optimally completes an optimal whole.

The second is shared with dynamic programming. The first is what greedy adds, and it is the one that fails.

The practical tool for establishing it is the exchange argument, and it is worth being able to run through:

1. Take any optimal solution O that does not contain the greedy choice.
2. Show you can swap the greedy choice into O, removing whatever conflicts with it.
3. Show the result is still valid and no worse.
4. Therefore an optimal solution containing the greedy choice exists.

Interval scheduling is the classic. To fit the most non-overlapping meetings in one room, take the one that ends earliest. Why: if some optimal schedule starts with a different meeting, that meeting ends no earlier, so replacing it with the earliest-ending one cannot conflict with anything that followed — the count is unchanged and the room is free sooner. That is the exchange argument in two lines. Intervals covers the mechanics; this is why the rule is sort by end rather than by start.

When it fails#

Greedy fails when a local choice can foreclose a better future — and the failure is silent, because the code still runs and still returns something.

The standing example is Coin Change. With denominations 1, 3 and 4 and a target of 6, greedy takes the largest coin that fits: 4, then 1, then 1 — three coins. The optimum is 3 + 3, which is two. There is no repair to the greedy rule that fixes this; the information needed to make the first choice correctly is not available until the rest is solved, which is exactly what dynamic programming is for.

0/1 knapsack fails the same way. Taking items by best value-per-weight is right when items can be split, and wrong when they cannot — one heavy, high-value item may beat several efficient light ones, and no local ratio reveals that.

The tell is the same in both: a choice made now changes what is affordable later. If the remaining problem after your greedy choice is not independent of which choice you made, greedy is probably wrong.

Greedy or DP?#

They solve overlapping sets of problems, and the trade is simple:

• Greedy commits. One pass, O(1) state, no memory of what it discarded. Fast, short, and wrong unless the choice property holds.
• DP keeps every option. It explores all the choices greedy would have thrown away, at the cost of a table and the time to fill it.

So the decision procedure is: try to state a greedy rule and prove it with an exchange argument. If the proof works, you have the faster solution. If you cannot construct the argument in a couple of minutes, use DP — a correct O(n·k) beats an unprovable O(n).

It is worth saying that out loud in an interview, because “I think greedy works here, and here’s why” followed by “if that argument is wrong, the fallback is a DP over these states” is a stronger answer than either solution alone.

The other habit worth having: try to break your own rule with a small counterexample before committing. Two or three adversarial inputs — a large value late, a tie, an element that looks attractive and is a trap — take under a minute and catch most bad greedy rules.

The shapes that show up#

Nearly every greedy problem here is one of five.

Carry a running best. One scan, one or two variables, a local comparison. The stock problem above; also Maximum Subarray, where the local decision is extend the current run or start fresh at this element — start fresh exactly when the running sum has gone negative, because a negative prefix can only hurt whatever follows. Kadane’s algorithm is usually presented as DP with O(1) state, and it is; it is also a greedy rule with a one-line proof. Both readings are correct and the second is easier to recall under pressure.

Sort, then take. The order is the algorithm. Sort by the right key and a single pass of “take it if it fits” is optimal. Choosing the key is the whole problem — see sorting and intervals.

Always take the most X. When the “best available” changes after every step, a heap supplies it. Task Scheduler runs the task with the most copies remaining, because the task you have most of is the one that will strand you at the end if you save it.

Count greedily. Longest Palindrome: every character with an even count contributes all of its copies, and one odd-count character can sit in the middle. No search — the answer follows from the tally directly, and the local rule (“take everything you can from each letter”) is trivially safe because letters do not compete.

Move the constrained side. Container With Most Water moves the pointer at the shorter line, and the justification is an exchange argument: that line caps the area for every pair it belongs to, so keeping it can never help — every remaining container using it is narrower and no taller. Two pointers covers the mechanics; this is why the move is provably safe rather than a heuristic.

Recognising it#

Consider greedy when:

• The problem asks for a maximum, minimum, or count — an optimum, not a list of everything.
• There is an obvious “best next step”, and taking it visibly shrinks the problem.
• The answer feels like it should be one pass, possibly after a sort.
• The constraints are too large for DP — n in the millions, where even an O(n) table is awkward. A greedy rule is often the intended solution when the input size rules everything else out.

And the check in the other direction: if a choice changes what is available later in a way that depends on which choice you made, expect greedy to fail, and reach for DP. If the problem wants all valid arrangements rather than the best one, it is backtracking, and greedy does not apply at all.

Summary#

Greedy is a proof obligation wearing a loop. The rule is easy; the argument that the rule is safe is the work, and the exchange argument is how you produce it — swap your choice into any optimal solution and show nothing gets worse. Where that argument exists, greedy is the shortest and fastest solution available. Where it does not, the failure is quiet, the code still returns an answer, and dynamic programming is the fallback. Try to break your own rule before you trust it.