Greedy

What it is

A greedy algorithm builds a solution by making one irreversible, locally-determined choice at a time — buy at the lowest price seen so far, keep the interval that ends earliest, cut the schedule at the first "peak" digit — and never revisits that choice. It works only when the problem has a structural guarantee that the locally best move is also part of some globally optimal solution. The technique itself is a one-pass or two-pass scan with O(1) or O(log n) extra bookkeeping per step; the hard part is never the loop, it's the argument for why the loop is allowed to stop looking back.

When it applies

• The problem asks for a minimum or maximum over choices made in sequence, and a "later" choice can never undo the benefit of an earlier correct one (buy-low-sell-high, interval scheduling, jump reachability).
• A quantity is monotone in some parameter (a bigger fuel budget never needs more stops; a looser sum budget never needs more pieces), which is what licenses binary search paired with a greedy feasibility check.
• It does not apply once a choice's value depends on a global trade-off between distant elements that can't be resolved locally — weighted interval scheduling or counting all arrangements need dynamic programming instead, and a greedy that looks right on small examples (like removing the longest interval, or starting at the largest local surplus) can be flatly wrong; always look for the counterexample before trusting intuition.

Tells in the problem

• "Return the maximum profit from at most one transaction" or similar single-pass optimization over a sequence — track a running best-so-far, don't enumerate pairs.
• "Minimum number of intervals/items to remove so the rest satisfy some pairwise condition" — sort by one endpoint and sweep, keeping the option that leaves the most room.
• "A circular arrangement where you must find a valid starting point" — a running-total reset argument, not a full O(n²) simulation.
• "Assign the fewest/most X units subject to a local ordering constraint between neighbors" — a directional scan (or two, one per direction) that only ever increases the tentative answer.
• Any prompt that pairs naturally with "prove this greedy choice is always safe" or "give a counterexample to this heuristic" — that phrasing itself signals the interviewer wants the exchange argument, not just working code.

The classic mistake

The mistake is coding the first greedy rule that seems plausible without checking it against an adversarial example, especially when a constraint is one-directional (a neighbor comparison, a single cooldown) but the real problem is symmetric or has a second direction. A single left-to-right pass that only enforces "bigger than my left neighbor gets more" silently breaks the mirrored right-side constraint, and a rule like "start where the local surplus is largest" can fail on inputs where the biggest local advantage still runs out of resources two steps later. It happens because the greedy's plausibility is easy to confirm on the example in the prompt and hard to break without deliberately constructing a case where an early strong choice causes a later failure. Before trusting a greedy, try to construct that adversarial case yourself, and if the constraint has two sides (left/right, before/after), ask whether one pass truly covers both or whether you need two.

Questions to start with

• Best Time to Buy and Sell Stock — the simplest form: one running minimum, one running best profit, no proof needed beyond "sell only improves against the cheapest buy so far."
• Jump Game — the greedy tracks a frontier instead of a path, showing that you don't have to choose which move to take to prove reachability.
• Non-overlapping Intervals — the exchange argument in its clearest form, plus the standard counterexample for why sorting by the wrong endpoint fails.
• Gas Station — a single reset-on-failure scan, with a proof that skips over a stretch of impossible starting points instead of testing each one.
• Candy — two directional passes combined with max, for a constraint that a single pass cannot satisfy on its own.