Take the best-looking option right now and never look back. When that is safe, it beats every other approach on speed and code size. The whole skill is knowing when it is safe.
Greedy code is short. Usually one pass, sometimes a sort first, and a running number or two. The hard part is not the code. It is the argument that the local choice can never cost you the global optimum. Without that argument, a greedy answer is a guess.
Interval scheduling: keep the most non-overlapping meetings. Greedy picks the meeting that ends first.
X. Call greedy’s first pick G.G ends no later than X, because greedy chose the earliest end of all.X out and G in. Every later meeting started after X ended, so it also starts after G ends. Nothing new overlaps.Reading the figure. Each bar is a meeting on a time line. Red X is the first meeting of some best schedule. Amber G is greedy’s first pick. The dashed lines show that G ends before X does. Y and Z start after X ends, so they also start after G ends. The green row keeps the same count with no clash.
That is the template for every greedy proof: swap in the greedy choice, nothing breaks, nothing gets worse. The full solution is Non-overlapping Intervals on page 04, which was a greedy all along.
[1, 3, 4] and amount 6. Largest-coin-first takes 4 + 1 + 1, three coins. The best answer is 3 + 3, two coins. The swap fails: replacing a 3 with the bigger 4 leaves a remainder that costs more coins. When you cannot make the swap work, try a small counterexample. If one turns up, switch to DP.def greedy_coin_count(coins: list[int], amount: int) -> int:
"""Largest coin first. Shown only to prove greedy can be wrong.
Args:
coins: Positive denominations, unlimited supply of each.
amount: Target sum, amount >= 0.
Returns:
The number of coins greedy uses, or -1 if greedy gets stuck.
Example:
>>> greedy_coin_count([1, 3, 4], 6)
3
>>> greedy_coin_count([5, 2], 6)
-1
"""
count = 0 # 0: no coins used yet
# The greedy choice: biggest coin first. reverse=True sorts high to low.
# Invariant: count coins already sum to (original amount - amount).
for coin in sorted(coins, reverse=True):
count += amount // coin # // : how many of this coin fit, rounded down
amount %= coin # %: what is left after taking those coins
# 0 left means greedy hit the target. Anything else means stuck: -1.
return count if amount == 0 else -1
The second example is worse than wrong. Greedy takes one 5, is left with 1, and gives up, even though 2 + 2 + 2 works. DP gets both right.
def greedy_scan(items: list[int]) -> int:
"""Walk once, keep one running number, never go back."""
# initial: the summary before any item is seen.
# Jump Game: reach = 0. Gas Station: tank = 0.
state = initial
# i is the position, item is the value there.
# Invariant: state is correct for items[0..i-1] at the top of every pass.
for i, item in enumerate(items):
# stuck(state, i): the summary proves we cannot go on.
# Jump Game: i > reach, so index i is a wall.
if stuck(state, i):
# give_up: the failure answer. Jump Game: False.
return give_up
# extend(state, i, item): fold this item in, keeping the best option.
# Jump Game: max(reach, i + item), the farther of old and new reach.
state = extend(state, i, item)
# finish(state): turn the summary into the answer. Jump Game: True.
return finish(state)
Jump Game, Gas Station and Partition Labels all fit this shape. The thinking goes into choosing state. Once you have it, the loop writes itself.
def greedy_by_sort(items: list[tuple[int, int]]) -> int:
"""Sort so the safest choice comes first, then take greedily."""
chosen = 0 # 0: nothing taken yet
# boundary: the limit before anything is taken.
# Interval scheduling: float("-inf"), so the first meeting always fits.
last = boundary
# sort_key: the order the exchange argument needs.
# Interval scheduling: the end time, item[1].
# Invariant: chosen is the best count for the items seen so far.
for item in sorted(items, key=sort_key):
# fits(item, last): item does not clash with what we kept.
# Interval scheduling: item[0] >= last, it starts after the last end.
if fits(item, last):
chosen += 1 # 1: this item joins the answer
# update(item): the new limit. Interval scheduling: item[1].
last = update(item)
return chosen
Reading the figure. Rows are in the order the loop sees them, sorted by end time. Green bars are taken. Red bars start before last, so they clash and are skipped. The dashed amber lines mark last after each take, at 4 and then 7. Notice that each take ends as early as it can, which leaves the most room on the right.
The sort carries the proof. Sort by end and interval scheduling is optimal. Sort by start or by length and it is not. Always say why you picked the key.
i + 1, not start + 1. Every station in between is ruled out too.start to end inclusive has end - start + 1 items.You stand on index 0 of an array. Each value nums[i] is the longest jump allowed from index i. Shorter jumps are also allowed. Return whether you can reach the last index.
reach, the farthest index that any route can land on so far.reach, no route gets here, so the answer is False.reach to i + nums[i] if that is farther.reach is reachable, because you can always jump short. So one number sums up all routes.def can_jump(nums: list[int]) -> bool:
"""Whether the last index is reachable from index 0.
Args:
nums: Non-negative jump lengths. nums[i] is the longest jump from i.
Returns:
True if some sequence of jumps lands on the last index.
Example:
>>> can_jump([2, 3, 1, 1, 4])
True
>>> can_jump([3, 2, 1, 0, 4])
False
"""
# reach: the farthest index any route found so far can land on.
# 0: we start on index 0, so it is reachable for free.
reach = 0
# i is the index we stand on. jump is the longest hop allowed from it.
# Invariant: every index 0..reach is reachable using nums[0..i-1].
for i, jump in enumerate(nums):
# i beyond reach: no earlier index can hop this far. i is a wall.
if i > reach:
return False
# From i we can land anywhere up to i + jump. Keep the farther reach.
reach = max(reach, i + jump)
# We never hit a wall, so the last index, len(nums) - 1, was reached.
return True
nums = [3, 2, 1, 0, 4]:
i = 0, jump 3: reach becomes 3.i = 1, jump 2: 1 + 2 = 3, reach stays 3.i = 2, jump 1: 2 + 1 = 3, reach stays 3.i = 3, jump 0: reach stays 3. Every route ends here.i = 4: 4 > 3, a wall. Return False.Reading the figure. Each blue arc is the longest jump from its index, ending at i + nums[i]. All three arcs land on index 3, the amber cell with jump 0. The green bar is reach. Index 4, in red, sits past the bar, so the loop returns False there.
def min_jumps(nums: list[int]) -> int:
"""Jump Game II: fewest jumps to reach the last index.
Args:
nums: Non-negative jump lengths. The last index is reachable.
Returns:
The minimum number of jumps.
Example:
>>> min_jumps([2, 3, 1, 1, 4])
2
"""
jumps = 0 # 0: no jumps taken yet
window_end = 0 # 0: with zero jumps we can only be on index 0
farthest = 0 # 0: farthest index reachable with one more jump
# Stop before the last index: len(nums) - 1. Standing on it needs no jump.
# Invariant: indexes up to window_end are reachable in `jumps` jumps.
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i]) # best landing from this window
# i == window_end: this window is used up. Take one more jump.
if i == window_end:
jumps += 1 # 1: one jump moves us to the next window
window_end = farthest # the next window ends at the best landing
return jumps
This is BFS by levels without a queue. Each window is one level. Say that link out loud.
True.0 at index 0 with more elements: stuck at once. The loop returns False at i = 1.0 in the middle is only a problem if nothing jumps over it.True as soon as reach >= len(nums) - 1. Same big-O, faster in practice.n stations sit on a circle. Station i gives gas[i] fuel, and driving to station i + 1 costs cost[i]. You start with an empty tank. Return the start index that lets you drive one full loop, or -1. The answer is unique if it exists.
-1.start and suppose the tank goes negative after station i. Then no station from start to i can be the answer. Each one is reached with a tank of at least zero, so starting there with zero is no better.i + 1 and reset the tank. One pass.def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
"""Start station for one full loop, or -1 if none exists.
Args:
gas: Fuel gained at each station.
cost: Fuel spent driving from station i to station i + 1.
Returns:
The unique valid start index, or -1.
Example:
>>> can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
3
>>> can_complete_circuit([2, 3, 4], [3, 4, 3])
-1
"""
# Less fuel than distance overall: no start can work. -1 means "none".
if sum(gas) < sum(cost):
return -1
start = 0 # 0: the first candidate is station 0
tank = 0 # 0: we arrive at the candidate with an empty tank
# i is the station we leave from.
# Invariant: tank is the fuel left after driving from start through i - 1,
# and it never dropped below 0 on the way.
for i in range(len(gas)):
tank += gas[i] - cost[i] # fill up at i, then pay the drive to i + 1
# Below 0: start cannot reach i + 1. Nor can any station between
# start and i, since each was reached with tank >= 0 and still failed.
if tank < 0:
start = i + 1 # + 1: the next station is the first fresh hope
tank = 0 # 0: restart with an empty tank
# Total fuel covers total cost, so the last surviving start completes the loop.
return start
gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. Net per station is [-2, -2, -2, 3, 3]. Totals are 15 and 15, so an answer exists.
i = 0: tank -2. Fail. Start moves to 1.i = 1: tank -2. Fail. Start moves to 2.i = 2: tank -2. Fail. Start moves to 3.i = 3: tank 3.i = 4: tank 6. Loop ends. Return 3.Reading the figure. Each column is one station. Red bars are a tank that went below zero. Each red bar resets the tank and moves start one past the failure. Green bars are a tank that stayed at zero or above. The green station cell is the answer, the last start that never failed.
gas[0] >= cost[0], and the code returns 0.<, not <=.sum calls are a second pass. You can fold them into the loop as a running total if asked.Split a string into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.
end as the farthest such index.i reaches end, every letter in the part is finished. Cut right there.end. Cutting at end leaves the most room for later parts, so it can only add parts.def partition_labels(s: str) -> list[int]:
"""Sizes of the most parts where no letter spans two parts.
Args:
s: The string to split.
Returns:
Part sizes, left to right. They sum to len(s).
Example:
>>> partition_labels("ababcbacadefegdehijhklij")
[9, 7, 8]
>>> partition_labels("abc")
[1, 1, 1]
"""
# last[ch]: the final index of ch. A part holding ch must reach it.
# Later indexes overwrite earlier ones, so the dict keeps the last.
last = {ch: i for i, ch in enumerate(s)}
sizes: list[int] = []
start = 0 # 0: the first part begins at index 0
end = 0 # 0: so far the part only has to reach index 0
# i is the index we read.
# Invariant: end is the farthest last-index of any letter in s[start..i].
for i, ch in enumerate(s):
end = max(end, last[ch]) # this letter may push the cut later
# i == end: every letter in this part is finished. Cut here.
if i == end:
sizes.append(end - start + 1) # + 1: both ends are inclusive
start = i + 1 # + 1: the next part starts after i
return sizes
s = "ababcbacadefegdehijhklij":
a: last a is at 8, so end = 8.b ends at 5, c at 7. Neither passes 8.i == end. Cut. Size 8 - 0 + 1 = 9.d: ends at 14. Then e at 15 pushes end to 15. Cut at 15, size 7.h: ends at 19. Then i (last at 22) and j (last at 23) push end to 23. Cut at 23, size 8.Reading the figure. Each cell is one letter, with its index below. Amber cells are last copies that set or push end. The label above each part shows how end grew. A red line is a cut, made the moment i == end. The green numbers are the answer.
[].A CPU runs tasks given as letters. Each slot runs one task or stays idle. Two runs of the same task need at least n slots between them. Return the fewest slots needed to run every task. Order is free.
A appears top times. Lay it out in top rows, one A per row.n + 1 slots wide: the A plus n cooling slots.top. That gives (top - 1) * (n + 1) + ties.len(tasks).from collections import Counter
def least_interval(tasks: list[str], n: int) -> int:
"""Fewest CPU slots to run all tasks with cooldown n between repeats.
Args:
tasks: Task labels. Repeats are allowed.
n: Minimum number of slots between two runs of the same task.
Returns:
The minimum total slots, idle slots included.
Example:
>>> least_interval(["A", "A", "A", "B", "B", "B"], 2)
8
>>> least_interval(["A", "A", "A", "B", "B", "B"], 0)
6
"""
# No tasks: no slots. 0 also keeps max() below off an empty list.
if not tasks:
return 0
counts = Counter(tasks)
# top: how many times the most common task must run.
top = max(counts.values())
# ties: how many tasks share that top count. They all sit in the last row.
ties = sum(1 for count in counts.values() if count == top)
# top - 1: full rows. The last row needs no cooldown after it.
# n + 1: each full row is the task plus n cooling slots.
frame = (top - 1) * (n + 1) + ties
# Too many tasks to fit the gaps: rows widen, no idle, answer = task count.
return max(frame, len(tasks))
tasks = A A A B B B, n = 2:
top = 3 (A and B each appear 3 times). ties = 2.top - 1 = 2, each n + 1 = 3 wide. That is 6 slots.A B, 2 slots. Frame is 8.A B idle | A B idle | A B. 6 tasks fit, so max(8, 6) = 8.n = 0 the frame is 2 * 1 + 2 = 4, below 6. No cooldown means no idle, so the answer is 6.Reading the figure. Each row starts with A and is n + 1 slots wide. So n slots always sit between two runs of A. Dashed cells are idle slots that nothing could fill. The green last row holds the tied tasks. The bottom strip is the same schedule read left to right.
n = 0: the answer is always len(tasks), and the max handles it.k times: (k - 1) * (n + 1) + 1.len(tasks). Many candidates miss this case.0 from the guard.[1, 3, 4], amount 6 is the one to quote. Then switch to DP.Greedy works on values. Pattern 18, the Trie, works on the shape of strings: a tree keyed by characters that stores shared prefixes once. It turns “which words start with this?” into a walk of a few steps.