At each step, take the locally optimal choice and never look back. Greedy is fast — often O(n) or O(n log n) after a sort — but it is only correct when you can prove via an exchange argument that no future step could benefit from a different earlier decision.
Greedy works when the locally best move can never foreclose the global best. If you can argue that any optimal answer could be rewritten to start with your choice without getting worse, you never need to look back — just take it and keep walking.
DP and greedy face the same fork at every step: which choice do I make now? DP explores all of them and remembers the sub-answers, because the choices interact — picking one changes what the others are worth. Greedy bets that they don't interact: it grabs the single best-looking option, throws the rest away, and never reconsiders.
That's the whole trade. When the bet holds, greedy is a sort plus one linear pass — dramatically simpler and faster than a table. When it doesn't, greedy is confidently wrong. So the algorithm is the easy part; the entire game is the justification.
Jump Game. Keep one number: the farthest index you can reach so far. Walk left to right; at each index push the bar out to i + nums[i]. You only lose if your foot lands past the bar:
nums = [ 2 ][ 3 ][ 1 ][ 1 ][ 4 ] index 0 1 2 3 4 i=0 stand on 0, jump up to +2 reach ▓▓▓▓▓▓░░░░ (farthest = 2) i=1 0..2 covered, jump +3 reach ▓▓▓▓▓▓▓▓▓▓ (farthest = 4) ← already home i=2 inside the bar reach ▓▓▓▓▓▓▓▓▓▓ i=3 inside the bar reach ▓▓▓▓▓▓▓▓▓▓ i=4 == last index → TRUE The rule: at each i, if i is still under the bar, push the bar out to i+nums[i]. The moment i pokes past the bar, you are stranded → FALSE.
Interval scheduling. To keep the most non-overlapping meetings, sort by earliest finish, sweep the timeline, and drop anything that overlaps what you already took. Finishing soonest leaves the most room for what comes next:
meetings (sorted by finish time): time 0 1 2 3 4 5 6 7 8 9 A [===] finishes @2 → TAKE (lastEnd = 2) B [=====] starts @1 < 2 → DROP (overlaps A) C [===] starts @3 ≥ 2 → TAKE (lastEnd = 5) D [=====] starts @4 < 5 → DROP (overlaps C) E [===] starts @6 ≥ 5 → TAKE (lastEnd = 8) kept = A, C, E (3 meetings). Picking the soonest-finishing meeting each time can never lose: any other first pick ends later, leaving less room.
lastEnd) and a rule that only ever moves it in the safe direction. No table, no backtracking — one sweep.When a problem smells greedy, don't just code the obvious move. Climb these rungs — the goal is to either earn the commitment or catch yourself before you ship a plausible-but-wrong solution:
is there an obvious "best next move"? # the candidate greedy choice
|
+-- can I argue a swap toward it never hurts?
| (exchange: rewrite any optimal answer to START with my
| choice without getting worse → my choice is safe)
|
+-- can I break it on a small case?
| (try {1,3,4} coins, weird intervals, all-negatives ...)
|
+-- choice survives & choices don't interact → GREEDY: commit, sweep
+-- a counterexample exists / choices interact → fall back to DPThe signature greedy disaster: a move that obviouslyseems best but isn't. Coin change makes it vivid. With coins {1, 3, 4}, “take the biggest coin that fits” feels unarguable — and is wrong:
make 6 with coins {1, 3, 4}
GREEDY : take biggest ≤ 6 → 4, remainder 2 → 1+1 = 4 + 1 + 1 (3 coins)
OPTIMAL : 3 + 3 = 3 + 3 (2 coins)
The locally "best" first coin (4) foreclosed the better pairing (3+3).
Choices INTERACTED → greedy is wrong here → this one needs DP.Grabbing the 4 foreclosed the better 3+3. The choices interacted: the first coin changed what the rest could do. That is the exact condition under which greedy breaks and DP is required. (With US-style coins {1, 5, 10, 25} the same greedy isprovably correct — which is why “it worked on my examples” is not a proof.)
The habit that separates a justified greedy from a lucky one: say, in one sentence, the invariantyour single pass maintains — the property that's true after every step and that guarantees the final answer is optimal.
farthest = the largest index reachable using only positions 0..i; if iever exceeds it, no choice could have done better.”lastEndis the earliest finish achievable for this many meetings — staying ahead means I never block a future one needlessly.”i, no start in [start..i] can work, so the only candidate left is i+1.”People file Kadane under DP, but it's pure greedy with a tiny invariant. Walk the array carrying the best sum ending at the current index. At each element make one local decision: extend the run, or start fresh here.
The invariant — “cur is the best subarray sum ending exactly at i” — is what makes the reset safe: a negative prefix never helps a later subarray, so abandoning it costs nothing. Same shape powers Gas Station and Partition Labels: carry a running quantity, reset the moment keeping it can only hurt.
A greedy algorithm processes items one by one and at each step picks the option that looks best right now, permanently committing to that choice. Unlike dynamic programming, it never stores alternative sub-answers and never revisits a decision.
The result is elegantly simple code — usually a sort followed by a single linear pass — and near-optimal runtime. The danger is that "best right now" must actually be "best overall," and that requires a proof, not just intuition.
A related technique is the stay-ahead argument: show that after every step the greedy solution is at least as far ahead (larger coverage, smaller cost, etc.) as any other algorithm. Classic example: earliest-finish-time interval scheduling.
If you cannot construct either argument — and especially if you find a small counterexample — the problem likely requires dynamic programming.
Greedy succeeds when choices are independent — picking an item (or interval, or step) does not change the value of remaining choices in a way that requires re-evaluation. When choices interact, DP is the right tool.
The cleanest mental model: DP builds a table of all reachable sub-states so that every path through the problem is considered. Greedy follows a single path, discarding all others the moment it makes a choice.
[1,4] [3,5] [0,6] [5,7] [3,9] [8,9]. Soonest finish, never look back.Reach for greedy when the problem asks you to maximize or minimize something and there is an obvious "best next" move that never hurts future steps. The key question is always: can I prove that committing to this choice now cannot make things worse later?
| "maximize / minimize" with an obvious "best next" local choice | sort by the relevant key, sweep greedily, prove with exchange argument |
| scheduling / intervals — pick the most compatible next interval | sort by earliest finish time, greedily accept non-overlapping intervals |
| "can you reach the end?" / jump game style reachability | track farthest reachable index in a single pass — no DP needed |
| "can you always do X?" / feasibility with a running resource | running balance: reset candidate start when balance goes negative |
| fewest coins / minimum steps with canonical or structured denominations | greedy only if exchange argument holds for those specific values |
| "partition / assign to groups" satisfying a local rule | sort + sweep: extend the current partition greedily until the rule breaks |
| "valid / possible with wildcards" — track a range of possible states | maintain [lo, hi] bounds of a running count; clamp at 0; fail if lo > max |
O(n·W) DP.When → The most common greedy shape. Sort items by the key that makes the exchange argument work (earliest end, smallest ratio, etc.), then make a single pass committing to items that pass a feasibility check.
function sortThenSweep<T>(items: T[], key: (x: T) => number): void {
items.sort((a, b) => key(a) - key(b)); // fix the order greedily
let state = initialState(); // whatever you're accumulating
for (const item of items) {
// make the locally optimal decision with the current item
if (feasible(item, state)) {
state = advance(state, item); // commit — no backtracking
}
// items that fail the feasibility check are simply skipped / rejected
}
}
// ── exchange argument reminder ──────────────────────────────────────────────
// To justify sorting by key k: assume an optimal solution has two adjacent
// items a, b with k(a) > k(b). Show that swapping them produces a result
// that is at least as good → the greedy order is safe.When → Reachability / coverage problems where each position extends your reach by some amount. Iterate left-to-right; if the current index exceeds farthest, it is unreachable.
function canReachEnd(nums: number[]): boolean {
let farthest = 0; // max index reachable so far
for (let i = 0; i < nums.length; i++) {
if (i > farthest) return false; // current pos is unreachable
farthest = Math.max(farthest, i + nums[i]);
}
return true;
}
// Variant — minimum jumps (BFS-by-levels):
function minJumps(nums: number[]): number {
let jumps = 0;
let curEnd = 0; // end of the current BFS level
let farthest = 0; // farthest index reachable within this level
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === curEnd) { // exhausted this level → must jump
jumps++;
curEnd = farthest;
}
}
return jumps;
}jumpsonly when the current position exhausts the current level's frontier.When → Resource-feasibility problems (gas station, circular tour). Accumulate a running net balance; whenever it goes negative, the current start is provably bad — reset the candidate start to the next position.
function findStart(gas: number[], cost: number[]): number {
let total = 0; // net gas across the whole circuit
let tank = 0; // running balance from the current candidate start
let start = 0;
for (let i = 0; i < gas.length; i++) {
const net = gas[i] - cost[i];
total += net;
tank += net;
if (tank < 0) { // can't reach i+1 from current start
start = i + 1; // greedy: the new candidate start is i+1
tank = 0; // reset the running balance
}
}
// if total >= 0 a solution exists and start is it; otherwise -1
return total >= 0 ? start : -1;
}When → Scheduling / non-overlapping interval problems. Sort by end time; greedily accept each interval whose start is >= lastEnd. The exchange argument: swapping the earliest-end interval for any other only delays lastEnd, never improves it.
function minGroups(intervals: [number, number][]): number {
// Sort by end time — taking the interval that finishes earliest
// leaves the most room for future intervals (classic exchange argument).
intervals.sort((a, b) => a[1] - b[1]);
let count = 0;
let lastEnd = -Infinity; // end of the last accepted interval
for (const [start, end] of intervals) {
if (start >= lastEnd) { // compatible with last chosen — take it
count++;
lastEnd = end;
}
// otherwise skip: this interval conflicts and taking it would only
// block more future intervals (it ends no earlier than lastEnd)
}
return count;
}The most dangerous greedy pitfall: "it feels like taking the biggest/smallest first should work." Always try to construct a counterexample or write down the exchange argument before coding. Plausible-but-wrong greedy solutions are a common interview failure mode.
Interval problems classically trip people up here: sorting by start time does not maximize the number of non-overlapping intervals — only sorting by endtime does. Let the exchange argument dictate the key, not intuition about what "seems natural."
When two items have equal sort keys, the tie-break can matter for correctness or for deduplication. Define a stable secondary sort key, or verify that the algorithm's result is the same regardless of tie order.
A single element trivially satisfies most greedy conditions — make sure the loop body still runs (or short-circuits correctly). All-negative inputs can break "reset on deficit" logic if the initial state is wrongly seeded at 0 instead of the actual first value. Always trace through the smallest valid inputs by hand.
curEnd (current level's frontier) and farthest (max reach within the level). Increment jumps when i === curEnd.#134Gas Station#134 · Medium — single pass running balance: when tank goes negative, reset start = i + 1. A solution exists iff the total net gas is non-negative, and the last surviving candidate is the answer.#846Hand of Straights#846 · Medium — sort and count, then greedily build consecutive groups of size groupSizestarting from the smallest available card. Use a frequency map; if the smallest card's count reaches zero before a full group is formed, return false.#1899Merge Triplets to Form Target Triplet#1899 · Medium — filter out any triplet that exceeds the target in any component (merging it could only corrupt the result), then OR the remaining triplets component-wise. The target is reachable iff the OR equals the target exactly.#763Partition Labels#763 · Medium — precompute the last occurrence of each character. Sweep left-to-right, extending the current partition end to lastOccurrence[c] for each seen character. When i === partitionEnd, close the partition and record its length.#678Valid Parenthesis String#678 · Medium — track a range [lo, hi] of possible open-paren counts. '(' increments both, ')' decrements both, '*' widens the range by ±1. Clamp lo at 0 (can't have negative opens). If lo > hi at any point, return false. Valid iff lo === 0 at the end.