The greedy intuition
Greedy is not a single algorithm — it's a design paradigm. At each step, you make the choice that maximizes (or minimizes) some local criterion, commit to it, and never look back. The correctness question is always: "does making the locally optimal choice now lead to a globally optimal result?" For many problems it does — and for those, greedy is much faster than DP.
Pattern 1 — Interval scheduling (sort by end time)
Problems involving intervals almost always use a greedy approach: sort by end time, then greedily select intervals that don't overlap. ```python # Non-overlapping Intervals (LC 435) — minimum removals def eraseOverlapIntervals(intervals): intervals.sort(key=lambda x: x[1]) # sort by end time end = float('-inf') removals = 0 for start, e in intervals: if start >= end: end = e # take this interval else: removals += 1 # skip (remove) this interval return removals ``` Why sort by end time? Selecting the interval that ends earliest leaves the most room for future intervals. Exchange argument: if we pick an interval with a later end instead, we can always swap it for the one with the earlier end without making things worse. Same pattern: Meeting Rooms II (LC 253 — use min-heap for room count), Minimum Arrows to Burst Balloons (LC 452).
Pattern 2 — Jump Game (reach-based greedy)
```python # Jump Game II (LC 45) — minimum jumps to reach end def jump(nums): jumps = 0 current_end = 0 # furthest we can reach with current jumps farthest = 0 # furthest we can reach with one more jump for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == current_end: jumps += 1 current_end = farthest return jumps ``` Jump Game I (LC 55) is even simpler: track max reachable index. If `i > max_reach`, return False.
Pattern 3 — Two-pass greedy
Some problems require a forward pass and a backward pass — neither alone gives the full picture. ```python # Candy (LC 135) — each child gets at least 1 candy; # children with higher rating than neighbors get more candies def candy(ratings): n = len(ratings) candies = [1] * n # Forward pass: ensure right neighbor with higher rating gets more for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # Backward pass: ensure left neighbor with higher rating gets more for i in range(n-2, -1, -1): if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1) return sum(candies) ``` Why two passes? A single left-to-right pass satisfies left-neighbor constraints. The backward pass then fixes right-neighbor constraints without breaking the left-neighbor ones (we take the max). Time: O(n). Space: O(n).
Pattern 4 — Gas Station (circular array greedy)
```python # Gas Station (LC 134) — find starting position to complete the circuit def canCompleteCircuit(gas, cost): if sum(gas) < sum(cost): return -1 # impossible: total gas < total cost tank = 0 start = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: # can't continue from start start = i + 1 # try starting from next station tank = 0 return start ``` Key insight: If total gas ≥ total cost, a solution exists. The greedy choice: whenever the tank goes negative, reset the start to the next station. If a solution exists, the accumulated positive balance from the last valid start covers the earlier negative sections. Time: O(n). This is a classic "reset start" greedy pattern.
When greedy fails — and you need DP
Greedy fails on the 0/1 Knapsack because items cannot be repeated and taking a high-value item now might prevent a better combination later. It fails on Longest Increasing Subsequence because the locally longest extension might not lead to the globally longest sequence. A good heuristic: if the problem involves "selecting a subset" where items interact with each other (one choice blocks another), think DP first. If the problem involves "scheduling, ordering, or extending a single running value greedily", think greedy first. Test: can you prove an exchange argument? If swapping any two adjacent choices in your greedy ordering never makes the result worse, your greedy is likely correct.