-
Notifications
You must be signed in to change notification settings - Fork 0
028 — Greedy
Picture a vending-machine attendant who needs to give you change using the fewest coins possible, with quarters, dimes, nickels, and pennies on hand. Their instinct — without doing any deep planning — is to grab the biggest coin that still fits under the remaining amount, over and over, until the amount hits zero. They never stop to consider "what if I used a nickel instead of a dime here, would that open up a better combination later?" They just trust that taking the locally best coin at every step adds up to the globally best total. For U.S. coin denominations, that trust is well-placed — it always works. That's the greedy pattern in one sentence: make the choice that looks best right now, never look back to reconsider it, and trust — having reasoned about why — that the chain of locally-best choices adds up to a globally-best answer.
Reach for greedy when you see:
- "Maximize" or "minimize" phrased as a sequence of choices, where you suspect — or can argue — that the locally best choice at each step never needs to be undone later. Greedy is a bet that no backtracking is required; if reconsidering an earlier choice ever seems necessary, that's a signal for DP or backtracking instead.
- The optimal strategy involves sorting first, then a single pass — "assign cookies to children to satisfy as many as possible," "minimum number of arrows to burst all balloons," "maximum number of non-overlapping intervals" — sort by some key (size, end time, start time), then greedily take or skip items in that sorted order.
- "Can you reach the end?" / "Jump Game"-style reachability — track "the furthest index reachable so far" and greedily extend it at each step, never needing to remember which earlier jump got you there, only how far it could take you.
- Problems that come with an informal proof sketch built in — "at each step, choose the option that..." combined with an intuitive argument for why that choice can never be worse than any alternative (an exchange argument: "if the optimal solution didn't make this choice, we could swap it in without making things worse").
The unifying tell: a provably safe local choice replaces the need to explore alternatives — often unlocked by sorting the input first — and once made, that choice is never revisited.
Jump Game — greedily tracking the furthest reachable index as you scan left to right, never re-examining a past decision:
nums: [2, 3, 1, 1, 4]
index: 0 1 2 3 4
i=0: nums[0]=2 -> can reach up to index 0+2=2 farthest = 2
i=1: nums[1]=3 -> can reach up to index 1+3=4 farthest = 4 (better, keep it)
i=2: nums[2]=1 -> can reach up to index 2+1=3 farthest stays 4
i=3: nums[3]=1 -> can reach up to index 3+1=4 farthest stays 4
i=4: farthest(4) >= last index(4) -> reachable! ✓
at every step: farthest = max(farthest, i + nums[i])
never need to remember WHICH jump produced the max — only the max itself
// Shape A: sort first, then make one greedy pass.
func greedySortTemplate(_ items: [(key: Int, value: Int)]) -> Int {
let sorted = items.sorted { $0.key < $1.key } // 🔧 Fill in: sort by whatever key makes the greedy choice safe
var result = 0
var state = 0 // 🔧 Fill in: whatever running state the greedy choice depends on
for item in sorted {
if item.key >= state { // 🔧 Fill in: the actual "is this choice safe/beneficial" condition
result += 1
state = item.value // 🔧 Fill in: update running state after taking this item
}
}
return result // 🔧 Fill in: return whatever the problem actually asks for
}
// Shape B: no sorting needed — track a single running "best so far" as you scan once.
func greedyRunningStateTemplate(_ nums: [Int]) -> Bool {
var best = 0 // 🔧 Fill in: whatever running "best so far" the greedy choice depends on
for i in 0..<nums.count {
if i > best { return false } // 🔧 Fill in: the actual failure condition, if any
best = max(best, i + nums[i]) // 🔧 Fill in: the actual greedy update rule
}
return true // 🔧 Fill in: return whatever the problem actually asks for
}Jump Game — given an array nums where nums[i] is the maximum jump length from index i, starting at index 0, return true if you can reach the last index.
func canJump(_ nums: [Int]) -> Bool {
var farthest = 0
for i in 0..<nums.count {
if i > farthest {
// Even the greediest possible play up to now can't reach index i.
return false
}
farthest = max(farthest, i + nums[i])
}
return true
}
// smoke test
print(canJump([2, 3, 1, 1, 4])) // true
print(canJump([3, 2, 1, 0, 4])) // false — stuck at index 3 (0-length jump), never reaches 4
print(canJump([0])) // true — already at the last index
print(canJump([1, 0, 1, 0])) // falseThis maps onto Shape B of the template directly: farthest is the single running piece of state the greedy choice depends on — "the furthest index reachable using any combination of jumps seen so far." At each index, the greedy move is simply farthest = max(farthest, i + nums[i]); there's no need to remember which earlier index produced that maximum, only the maximum itself, because any index that can reach further is strictly at least as good for every future decision. The only way to fail is if the scan reaches an index i that's beyond every jump made so far (i > farthest), meaning the array has a gap no prior greedy choice can bridge.
Greedy is the vending-machine attendant grabbing the biggest coin every time — commit to the locally best choice, never look back, and trust the proof that it can't hurt you.
"Gas Station" (given circular gas stations with gas[i] fuel gained and cost[i] fuel spent to reach the next station, find the starting station that lets you complete the full circuit, or return -1 if impossible) also has a greedy solution. Why does finding a station where the running fuel total first goes negative let you safely rule out every station up to and including that one as a possible starting point, rather than only ruling out that single station?
⬅️ Previous: 2D Dynamic Programming · Next: Matrix Traversal ➡️