Greedy (Furthest Reach & Running Best)
The Intuition
Some problems look like they need dynamic programming until you notice a single number is enough state. The whole problem reduces to one running variable that you update as you scan once. No DP table, no memoization, no branching. A local greedy choice is provably the global optimum, usually proved by a one-line exchange argument: any other choice gives a result that is no better.
The code below works through three LeetCode problems in this family.
Jump Game (LC 55). Given an array where each element is the maximum jump length from that position, return whether you can reach the last index starting from index 0. The running variable is the furthest index reachable so far. Walk left to right. At every index i, first check if i > furthest. If yes, you have already failed; nothing past this point is reachable. Otherwise update furthest = max(furthest, i + nums[i]). The moment furthest covers the last index, return true. One pass, one integer of state.
Best Time to Buy and Sell Stock (LC 121). Given an array of daily prices, find the maximum profit from a single buy-then-sell. The running variable is the lowest price seen so far. The maximum profit on day i equals prices[i] minus that running minimum. Track both at the same time, no further state needed.
Gas Station (LC 134). Given two arrays gas and cost representing a circular route, return the index of the station from which you can complete the loop without running out of gas, or -1 if no such start exists. The key insight: if your tank ever goes negative starting from station s, then no station between s and the failure point could have been a valid start either, so fast-forward to the next station after the failure. The total accumulator separately checks whether the round trip is even possible (sum of all gains and losses must be non-negative).
- The problem is on a 1D array and asks a yes/no or running-best question
- A single running scalar (max reach, min seen, accumulator) seems to capture all the state you need
- You can articulate why looking back at past elements would not change the answer
- DP would work but feels overkill
- The problem requires you to reconstruct the actual path or sequence (often DP is needed instead)
- Local optimum can be wrong (try a small example; if greedy fails, fall back to DP or BFS)
- Multiple greedy criteria conflict and you cannot pick one (use DP)
Variations:
- Jump Game II: Same setup but minimize the number of jumps. Track the current jump's reach and the next jump's reach as two variables.
- Stock with cooldown or fee: Now you need DP because the choice on day
idepends on dayi-1's state. - Two-direction greedy: Some problems (Trapping Rain Water, Candy) need a left-to-right pass and a right-to-left pass, then combine.
- Single element array
- All zeros (Jump Game returns true if length is 1, false otherwise)
- Strictly decreasing prices (max profit is 0)
- Empty input (return whatever the spec says, often 0 or true)
Key Points
- •Track a single running statistic as you scan once
- •For Jump Game, that statistic is the furthest index reachable so far
- •For Buy/Sell Stock, that statistic is the lowest price seen so far
- •Reject early if the running stat fails an invariant (cannot reach current index)
- •Greedy works when a local optimal choice never blocks the global optimum
Code Template
1 # Jump Game (LC 55). Can you reach the last index?
2 def can_jump(nums):
3 furthest = 0
4 n = len(nums)
5 for i in range(n):
6 if i > furthest:
7 return False
8 if i + nums[i] > furthest:
9 furthest = i + nums[i]
10 if furthest >= n - 1:
11 return True
12 return True
13
14 # Best Time to Buy and Sell Stock (LC 121). Single transaction.
15 def max_profit(prices):
16 min_price = float('inf')
17 profit = 0
18 for p in prices:
19 if p < min_price:
20 min_price = p
21 elif p - min_price > profit:
22 profit = p - min_price
23 return profit
24
25 # Gas Station (LC 134). Can you complete the circuit?
26 def can_complete_circuit(gas, cost):
27 total, tank, start = 0, 0, 0
28 for i in range(len(gas)):
29 diff = gas[i] - cost[i]
30 total += diff
31 tank += diff
32 if tank < 0:
33 start = i + 1
34 tank = 0
35 return start if total >= 0 else -1Common Mistakes
- Confusing this pattern with DP and writing an O(n^2) solution
- Updating the running stat with the wrong order relative to the answer update
- Returning false too early before checking the final position
- Forgetting that the array can have leading zeros (Jump Game still has to handle them)