Take the locally best choice at each step - and know how to argue it stays globally optimal.
What the greedy pattern is
A greedy algorithm commits to the best-looking choice at each step and never reconsiders. When it works, it beats DP on every axis - simpler code, better constants, usually O(n log n) from a sort or O(n) from a sweep. The catch is the word 'when': greedy is only correct if local choices can never paint you into a corner.
The justification has a standard shape, the exchange argument: take any optimal solution that disagrees with the greedy choice, swap in the greedy choice, and show the result is no worse. If that swap always works, greedy is optimal. Interviewers accept a crisp one-line version of this; hand-waving 'it seems right' is what they are probing for.
How to recognize it
Signals: scheduling and interval selection (sort by end time), 'minimum number of X to cover Y' (jump games, arrows through balloons), matching two sorted sequences against each other (cookies to children), and problems where sorting by the right key makes each decision obvious.
The recognition test is adversarial: spend thirty seconds trying to construct a counterexample where the local best kills the global best. Found one? DP. Can't - and can sketch why not? Greedy. Coins {1,3,4} for amount 6 is the canonical greedy-killer; interval scheduling by earliest end is the canonical greedy-winner.
The three recurring shapes
Sort-then-sweep: order items by the decisive key (interval end, deadline, size), then one pass making forced choices. Choosing the sort key is the entire problem - end time works for interval scheduling precisely because finishing earliest leaves maximal room for the rest.
Reachability sweep: track the furthest index reachable while scanning (jump game); a position beyond the reach is a 'no'. The layered version (jump game II) counts rounds, which is BFS thinking flattened into one array pass.
Two-pointer matching: with both sides sorted, satisfy the cheapest demand with the smallest sufficient supply - each assignment is safe by exchange.
pseudocode
# interval scheduling: max non-overlapping intervals
sort intervals by end
count = 0; lastEnd = -infinity
for (start, end) in intervals:
if start >= lastEnd:
count += 1
lastEnd = end
return count
Complexity
Dominated by the sort: O(n log n), then a linear sweep. Pure sweeps like jump game are O(n) with O(1) space. This is the practical reason to attempt a greedy before a DP: when both are correct, greedy's smaller state and better constants win.
Common pitfalls
Sorting intervals by start instead of end for selection problems - the long early interval blocks everything and the count suffers.
Asserting greedy correctness without even a sketch of an exchange argument - the fastest way to lose an interviewer's trust.
Missing the greedy-killer: applying largest-coin-first to arbitrary coin systems.
Off-by-one in reachability sweeps: a position is a dead end when it exceeds the running reach, checked before extending the reach with the current position.
Confusing 'maximize count of chosen items' (sort by end) with 'minimize removals' - they are the same problem, remove = total - chosen, but candidates often re-derive it badly under pressure.
Worked examples
1. Non-overlapping intervalsmedium
Given intervals, return the minimum number to remove so the rest don't overlap.
Flip it: minimizing removals = keeping the maximum number of non-overlapping intervals, which is classic interval scheduling.
Sort by end time. Exchange argument: any optimal kept-set's first interval can be swapped for the earliest-ending one without losing feasibility - earliest end leaves the most room.
Sweep: keep an interval when its start is at least the last kept end; otherwise it overlaps and is removed (count it).
Answer is the removal count. O(n log n) for the sort, O(1) extra space.
pseudocode
sort intervals by end
removed = 0; lastEnd = -infinity
for (start, end) in intervals:
if start >= lastEnd:
lastEnd = end # keep it
else:
removed += 1 # overlaps a kept one
return removed
Remember: Earliest-end-first is safe by exchange: swapping any kept interval for one ending sooner never reduces what still fits afterwards.
2. Jump gamemedium
Each array position holds a maximum jump length. Starting at index 0, can you reach the last index?
You never need to decide where each jump lands - only whether the frontier of reachability ever stalls before the end.
Sweep left to right maintaining reach = furthest index attainable so far. If the current index exceeds reach, you are standing somewhere unreachable: return false.
Otherwise extend: reach = max(reach, i + nums[i]). Reaching or passing the last index means true.
O(n) time, O(1) space. The DP formulation (can[i]) is O(n^2) and strictly worse - this is the problem where greedy replaces DP, not approximates it.
pseudocode
reach = 0
for i in 0 .. n-1:
if i > reach: return false
reach = max(reach, i + nums[i])
if reach >= n-1: return true
return true
Remember: Track the frontier, not the paths - reachability only ever grows, so one pass with a running maximum decides everything.
3. Assign cookieseasy
Each child has a greed factor and each cookie a size; a child is content if their cookie's size meets their greed. Maximize content children with one cookie each.
Sort both arrays. The safe move: satisfy the least greedy unmatched child with the smallest cookie that suffices.
Exchange argument: if an optimal assignment gives that child a bigger cookie, swapping to the smallest sufficient one frees the bigger cookie for someone greedier - never worse.
Two pointers: advance the cookie pointer always; advance the child pointer only on a successful match.
Matches counted = answer. O(n log n + m log m) for sorts, O(1) extra.
pseudocode
sort greed; sort sizes
child = 0
for cookie in sizes:
if child < len(greed) and greed[child] <= cookie:
child += 1 # matched
return child
Remember: Sorted supply against sorted demand: spend the smallest sufficient resource each time, and every swap argument favors you.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What is an exchange argument?
Swapping two loop variables to simplify code
✓ Showing that any optimal solution can be transformed to include the greedy choice without getting worse - hence greedy is optimal
Trading time complexity for space
Replacing recursion with iteration
It is the standard correctness proof for greedy: assume an optimal solution differs on the first decision, exchange in the greedy choice, verify feasibility and no loss. Repeating the swap aligns optimal with greedy entirely.
2Why does interval scheduling sort by end time rather than start time?
End times are usually distinct
✓ Finishing earliest leaves the maximum remaining room, so the earliest-ending compatible interval is always a safe pick
It makes the sweep O(n) instead of O(n log n)
Sorting by start is equivalent
The exchange: replace an optimal solution's first interval with the earliest-ending one; everything that fit before still fits. Sorting by start famously fails - one long early interval can block many short ones.
3Which observation converts jump game from O(n^2) DP into O(n) greedy?
Jumps can be sorted by length
✓ Only the furthest reachable frontier matters - individual jump choices never need to be fixed
The array contains no zeros
Binary search over the answer
Reachability is monotone: if index i is reachable, so is everything before it. A single running maximum of i + nums[i] captures the entire state that DP was tabulating.
4You suspect greedy but cannot find a proof sketch in the interview. Best move?
Code it anyway and hope
✓ Spend a moment hunting for a counterexample; if one appears, pivot to DP, and say that reasoning out loud
Switch to brute force
Ask for a hint immediately
The counterexample hunt is fast and decisive: it either yields the DP pivot (with justification) or builds confidence toward an exchange sketch. Narrating this is exactly the judgment interviewers score.
Frequently asked questions
How do I know if greedy is correct without a formal proof?
Attack it: try small adversarial inputs designed to make the local choice backfire. Surviving a genuine attempt plus a one-line exchange sketch ('swapping in the greedy pick never hurts because...') is the practical interview standard.
What is the relationship between greedy and DP?
Greedy is DP where the choice at each state needs no comparison - one option provably dominates. That is why the fallback direction is always greedy-to-DP: when the domination argument fails, enumerate the choices and cache.
Which sort key do I pick?
Pick the key that makes each sequential decision forced or obviously safe: end time for selections, deadline for scheduling penalties, size for matching problems. If no key makes decisions look forced, that is evidence against greedy.