Greedy (Exchange Argument, Furthest Reach)
Jump Game (LC 55)(opens leetcode.com)
You get an integer array nums and begin on index 0. The value nums[i] is the longest jump you may make from index i: from there you can move forward by any whole number of steps from 1 up to nums[i], and a value of 0 means you cannot move on from that index.
Return true if some sequence of jumps lands you on the last index, and false if every sequence gets stuck before it.
3 carries you straight to index 4, the last index. Other routes work too; one is enough.Greedy
choices in order ➔ locally best option (exchange argument) ➔ never undone| 1 | def can_jump(nums: list[int]) -> bool: |
| 2 | """Jump Game: greedy furthest reach. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | reach = 0 # Furthest index some run of jumps can land on so far |
| 6 | |
| 7 | for i in range(len(nums)): |
| 8 | # 1. Stop When Index i Is Unreachable, Otherwise Extend reach: |
| 9 | # An index past reach has no jump landing on it, so it must never extend reach with its own jump; |
| 10 | # check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always |
| 11 | # contains every index a shorter one does. |
| 12 | if i > reach: |
| 13 | return False |
| 14 | reach = max(reach, i + nums[i]) |
| 15 | |
| 16 | return True # The loop stood on every index, the last one included |
i is checked, reach is the furthest index any run of jumps from the indices before i can land on, and every index up to reach can be landed on.You never need the path, only how far any path can get: keep reach, the furthest index a run of jumps can land on so far, and at every index you can stand on extend it with reach = max(reach, i + nums[i]). A jump may be shorter than nums[i], so every index up to reach can be landed on and the reachable indices always form one block 0..reach; taking the larger reach can never cost an option, because a longer block contains every index of a shorter one. That is the greedy argument in general: the locally best choice keeps everything any other choice would keep, so it never has to be undone. The trap is the order of the two lines: check if i > reach: return False before reading nums[i], because an index past reach can't be stood on, and letting its jump extend reach makes [3,2,1,0,4] return True.
See it run
Greedy furthest reach, step by step
i -reach 0
The top row is nums. The bottom row marks the indices from 0 up to reach with the text ok. A blank cell is an index no run of jumps can land on yet.
ithe index being checked nowin reachan index that some run of jumps can land onreachthe furthest index that can be landed on (the last index when reach goes past it)
Start: reach = 0, because only index 0 can be stood on before any jump.
Gotcha 1 of 3
- The trap
Gotcha 1: Updating
reachbefore checkingi > reachMistakereach = max(reach, i + nums[i]) if i > reach: return FalseFixif i > reach: return False reach = max(reach, i + nums[i])What happens: An index past
reachcannot be stood on. So its jump must never count. Updating first lets that index extendreachwith its own jump. Theni > reachis False, and the loop goes on as if indexicould be reached.Example: nums = [3, 2, 1, 0, 4]Mistake: returns TrueFix: returns False
- Taking the locally best item can block a better pair later, as in House Robber (LC 198): robbing the richest house rules out both its neighbours, so earlier choices have to be weighed against each other instead of made once. See House Robber
- Each choice spends a limited budget and a later step can show it was the wrong one, as in Minimum Number of Refueling Stops (LC 871): you need a way to take a past pick back, which a plain greedy never does. See Greedy with Regret
Deep Dive
Why the locally best choice is safe: the exchange argument
A greedy algorithm makes one choice at each step and never takes it back. This is safe only when you can prove that the best choice now keeps every option that any other choice would keep. This proof is called the exchange argument. Take any complete answer that makes a different choice. Replace that choice with the greedy one. If the answer is still valid and no worse, then nothing was lost.
Jump Game (LC 55) is the plainest case. A jump from index i may be any length from 1 to nums[i], so the indices that can be landed on always form one block 0..reach. Two choices give two blocks. The longer block contains every index of the shorter one. So reach = max(reach, i + nums[i]) keeps everything the other value would keep, and it never has to be undone.
The same proof tells you when greedy is not allowed. If one choice can remove an option that another choice keeps, the exchange fails, and the choice may have to be taken back.
Example: nums = [2, 3, 1, 1, 4]. Index 0 gives reach = 2. Index 1 gives max(2, 1 + 3) = 4, which is the last index, so the answer is True. A shorter jump from index 1 would land on a block that is inside 0..4, so choosing the longest jump lost nothing.
One trace: check i > reach before the update
The board replays nums = [3, 2, 1, 0, 4]. The top row is nums. The bottom row marks the indices from 0 up to reach.
Index 0 raises reach from 0 to 3. Indices 1, 2 and 3 give 1 + 2 = 3, 2 + 1 = 3 and 3 + 0 = 3, so reach stays 3. Every jump ends at index 3 or earlier. Index 4 is outside the block.
At index 4 the check i > reach is 4 > 3, which is true, so the function returns False. This is the step marked as the trap on the board.
If the update ran first, index 4 would compute max(3, 4 + 4) = 8. Then 4 > 8 is false, and the loop would finish and return True. But no jump can land on index 4, so its own jump must not count. The right answer is False.
The same idea in Jump Game II, Gas Station and Partition Labels
The method is the same in every problem of this family. Find the choice that keeps the most options. Prove it with the exchange argument. Then make the choice once, in a single pass. The problems below look different, but each one has this shape.
Jump Game II (LC 45) asks for the fewest jumps. Keep end, the last index that the current number of jumps can reach, and far, the furthest index the next jump can reach. When i == end, take one more jump and set end = far. Taking the furthest far keeps every index a shorter jump would keep. For [2, 3, 1, 1, 4] the answer is 2.
Gas Station (LC 134) asks for a start station. Add gas[i] - cost[i] to a running tank. If tank becomes negative at station i, no start from the current start up to i can work, because each of them reaches i with a smaller tank. Skip them all and try i + 1. For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3.
Partition Labels (LC 763) asks for the most parts in which no letter appears in two parts. Keep end, the last position of any letter seen in the current part. When i == end, close the part. Closing as early as the rule allows gives the most parts. For "ababcbacadefegdehijhklij" the parts have sizes 9, 7 and 8.
When greedy fails, and the cost
A greedy choice fails when it uses up something that a later choice needs. In House Robber (LC 198), taking the richest house blocks both of its neighbours. For nums = [5, 8, 5], greedy takes 8 and stops with 8. The best answer is 5 + 5 = 10. Here the exchange fails, so the problem needs Dynamic Programming, which compares earlier answers.
Before you write a greedy solution, try to break it with a small input. Ask: can the best choice now remove an option that a different choice would keep? If you cannot find such an input and you can explain why, the exchange argument holds.
can_jump visits each index once and does constant work for each one. So the time is O(N), and the space is O(1) because it keeps only reach.
Example: an array of 100000 numbers takes 100000 checks, with no table and no recursion.
60-Second Pitch
"I only need to know how far any path can get, so I keep reach, the furthest index that some run of jumps can land on. A jump can be shorter than nums[i], so the landing indices always form one block from 0 to reach. At each index I first check i > reach. If it is true, nobody can stand on i, so I return False. Otherwise I set reach = max(reach, i + nums[i]). The larger reach contains every index of the smaller one, so the choice never has to be undone. That is the exchange argument. It is one pass, so the time is O(N) and the space is O(1)."
Common Questions
- How do I know a greedy solution is correct?
Use the exchange argument. Take any valid answer that makes a different choice at the first step. Replace that choice with the greedy one. If the answer stays valid and no worse, the greedy choice is safe. In Jump Game (LC 55), the larger
reachcontains every index of the smaller one, so the replacement always works.- How is greedy different from Dynamic Programming?
Greedy makes one choice at each step and never changes it. Dynamic Programming keeps answers for several choices and compares them later. If the best choice now can remove an option that a worse choice keeps, as in House Robber (LC 198), greedy fails and Dynamic Programming is needed.
- Why must
i > reachbe checked before the update? An index past
reachcannot be stood on, so its jump must not count. If the update runs first, that index extendsreachwith its own jump. For[3, 2, 1, 0, 4], index 4 would setreach = 8, the check would pass, and the function would return True instead of False.- What are the time and space complexity?
- In Jump Game II (LC 45), why not count every time
fargrows? A jump is counted when
ireachesend, the last index the current number of jumps can cover. Thenendbecomesfar. Counting every growth offarcounts growths that happen inside one jump. For[1, 2, 2, 1],fargrows three times, at index 0, 1 and 2, but the answer is 2.
SWE Reasoning
Spot it
- Each step offers a choice, such as how far to jump, where to start or where to cut.
- You can argue that one choice keeps every option the other choices would keep.
- The question asks whether something is possible, or for a minimum or maximum count, and not for the path itself.
- A search over all choices is far too slow, but one pass over the input in a fixed order looks enough.
- A small input where the best choice now blocks a better one later does not exist, or you can explain why.
The invariant, step by step
reach = 0. Only index 0 can be stood on, before any jump.- At index
i, the checki > reachruns first. If it is true, no jump lands oni, and the function returns False. - Otherwise
ican be stood on. Its jumps can land anywhere ini + 1..i + nums[i]. reach = max(reach, i + nums[i])joins that range to the block. The larger value contains every index of the smaller one.- The block
0..reachtherefore holds exactly the indices that some run of jumps can land on. - If the loop stands on every index, the last index is in the block, and the function returns True.
Traps
- Updating
reachbefore the check. An index pastreachmust not extend it. For[3, 2, 1, 0, 4]the wrong order returns True and the right answer is False. range(len(nums) - 1). The last index is never checked, so the same input returns True.reach = i + nums[i]withoutmax. A short jump after a long one lowersreach. For[4, 1, 0, 0, 0]the loop stops early and returns False instead of True.- Using greedy where the exchange fails. In House Robber (LC 198), the richest house is not always in the best answer.
- Stating the choice without the proof. "Take the biggest" is not an argument. Say what the greedy choice keeps that the other choices also keep.
Practice
Greedy (Exchange Argument, Furthest Reach)
Jump Game (LC 55)(opens leetcode.com)
You get an integer array nums and begin on index 0. The value nums[i] is the longest jump you may make from index i: from there you can move forward by any whole number of steps from 1 up to nums[i], and a value of 0 means you cannot move on from that index.
Return true if some sequence of jumps lands you on the last index, and false if every sequence gets stuck before it.
3 carries you straight to index 4, the last index. Other routes work too; one is enough.Greedy
choices in order ➔ locally best option (exchange argument) ➔ never undone| 1 | def can_jump(nums: list[int]) -> bool: |
| 2 | """Jump Game: greedy furthest reach. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | reach = 0 # Furthest index some run of jumps can land on so far |
| 6 | |
| 7 | for i in range(len(nums)): |
| 8 | # 1. Stop When Index i Is Unreachable, Otherwise Extend reach: |
| 9 | # An index past reach has no jump landing on it, so it must never extend reach with its own jump; |
| 10 | # check that first. Otherwise take the larger of reach and i + nums[i], since a longer reach always |
| 11 | # contains every index a shorter one does. |
| 12 | if i > reach: |
| 13 | return False |
| 14 | reach = max(reach, i + nums[i]) |
| 15 | |
| 16 | return True # The loop stood on every index, the last one included |
i is checked, reach is the furthest index any run of jumps from the indices before i can land on, and every index up to reach can be landed on.You never need the path, only how far any path can get: keep reach, the furthest index a run of jumps can land on so far, and at every index you can stand on extend it with reach = max(reach, i + nums[i]). A jump may be shorter than nums[i], so every index up to reach can be landed on and the reachable indices always form one block 0..reach; taking the larger reach can never cost an option, because a longer block contains every index of a shorter one. That is the greedy argument in general: the locally best choice keeps everything any other choice would keep, so it never has to be undone. The trap is the order of the two lines: check if i > reach: return False before reading nums[i], because an index past reach can't be stood on, and letting its jump extend reach makes [3,2,1,0,4] return True.
See it run
Greedy furthest reach, step by step
i -reach 0
The top row is nums. The bottom row marks the indices from 0 up to reach with the text ok. A blank cell is an index no run of jumps can land on yet.
ithe index being checked nowin reachan index that some run of jumps can land onreachthe furthest index that can be landed on (the last index when reach goes past it)
Start: reach = 0, because only index 0 can be stood on before any jump.
Gotcha 1 of 3
- The trap
Gotcha 1: Updating
reachbefore checkingi > reachMistakereach = max(reach, i + nums[i]) if i > reach: return FalseFixif i > reach: return False reach = max(reach, i + nums[i])What happens: An index past
reachcannot be stood on. So its jump must never count. Updating first lets that index extendreachwith its own jump. Theni > reachis False, and the loop goes on as if indexicould be reached.Example: nums = [3, 2, 1, 0, 4]Mistake: returns TrueFix: returns False
- Taking the locally best item can block a better pair later, as in House Robber (LC 198): robbing the richest house rules out both its neighbours, so earlier choices have to be weighed against each other instead of made once. See House Robber
- Each choice spends a limited budget and a later step can show it was the wrong one, as in Minimum Number of Refueling Stops (LC 871): you need a way to take a past pick back, which a plain greedy never does. See Greedy with Regret
Deep Dive
Why the locally best choice is safe: the exchange argument
A greedy algorithm makes one choice at each step and never takes it back. This is safe only when you can prove that the best choice now keeps every option that any other choice would keep. This proof is called the exchange argument. Take any complete answer that makes a different choice. Replace that choice with the greedy one. If the answer is still valid and no worse, then nothing was lost.
Jump Game (LC 55) is the plainest case. A jump from index i may be any length from 1 to nums[i], so the indices that can be landed on always form one block 0..reach. Two choices give two blocks. The longer block contains every index of the shorter one. So reach = max(reach, i + nums[i]) keeps everything the other value would keep, and it never has to be undone.
The same proof tells you when greedy is not allowed. If one choice can remove an option that another choice keeps, the exchange fails, and the choice may have to be taken back.
Example: nums = [2, 3, 1, 1, 4]. Index 0 gives reach = 2. Index 1 gives max(2, 1 + 3) = 4, which is the last index, so the answer is True. A shorter jump from index 1 would land on a block that is inside 0..4, so choosing the longest jump lost nothing.
One trace: check i > reach before the update
The board replays nums = [3, 2, 1, 0, 4]. The top row is nums. The bottom row marks the indices from 0 up to reach.
Index 0 raises reach from 0 to 3. Indices 1, 2 and 3 give 1 + 2 = 3, 2 + 1 = 3 and 3 + 0 = 3, so reach stays 3. Every jump ends at index 3 or earlier. Index 4 is outside the block.
At index 4 the check i > reach is 4 > 3, which is true, so the function returns False. This is the step marked as the trap on the board.
If the update ran first, index 4 would compute max(3, 4 + 4) = 8. Then 4 > 8 is false, and the loop would finish and return True. But no jump can land on index 4, so its own jump must not count. The right answer is False.
The same idea in Jump Game II, Gas Station and Partition Labels
The method is the same in every problem of this family. Find the choice that keeps the most options. Prove it with the exchange argument. Then make the choice once, in a single pass. The problems below look different, but each one has this shape.
Jump Game II (LC 45) asks for the fewest jumps. Keep end, the last index that the current number of jumps can reach, and far, the furthest index the next jump can reach. When i == end, take one more jump and set end = far. Taking the furthest far keeps every index a shorter jump would keep. For [2, 3, 1, 1, 4] the answer is 2.
Gas Station (LC 134) asks for a start station. Add gas[i] - cost[i] to a running tank. If tank becomes negative at station i, no start from the current start up to i can work, because each of them reaches i with a smaller tank. Skip them all and try i + 1. For gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] the answer is 3.
Partition Labels (LC 763) asks for the most parts in which no letter appears in two parts. Keep end, the last position of any letter seen in the current part. When i == end, close the part. Closing as early as the rule allows gives the most parts. For "ababcbacadefegdehijhklij" the parts have sizes 9, 7 and 8.
When greedy fails, and the cost
A greedy choice fails when it uses up something that a later choice needs. In House Robber (LC 198), taking the richest house blocks both of its neighbours. For nums = [5, 8, 5], greedy takes 8 and stops with 8. The best answer is 5 + 5 = 10. Here the exchange fails, so the problem needs Dynamic Programming, which compares earlier answers.
Before you write a greedy solution, try to break it with a small input. Ask: can the best choice now remove an option that a different choice would keep? If you cannot find such an input and you can explain why, the exchange argument holds.
can_jump visits each index once and does constant work for each one. So the time is O(N), and the space is O(1) because it keeps only reach.
Example: an array of 100000 numbers takes 100000 checks, with no table and no recursion.
60-Second Pitch
"I only need to know how far any path can get, so I keep reach, the furthest index that some run of jumps can land on. A jump can be shorter than nums[i], so the landing indices always form one block from 0 to reach. At each index I first check i > reach. If it is true, nobody can stand on i, so I return False. Otherwise I set reach = max(reach, i + nums[i]). The larger reach contains every index of the smaller one, so the choice never has to be undone. That is the exchange argument. It is one pass, so the time is O(N) and the space is O(1)."
Common Questions
- How do I know a greedy solution is correct?
Use the exchange argument. Take any valid answer that makes a different choice at the first step. Replace that choice with the greedy one. If the answer stays valid and no worse, the greedy choice is safe. In Jump Game (LC 55), the larger
reachcontains every index of the smaller one, so the replacement always works.- How is greedy different from Dynamic Programming?
Greedy makes one choice at each step and never changes it. Dynamic Programming keeps answers for several choices and compares them later. If the best choice now can remove an option that a worse choice keeps, as in House Robber (LC 198), greedy fails and Dynamic Programming is needed.
- Why must
i > reachbe checked before the update? An index past
reachcannot be stood on, so its jump must not count. If the update runs first, that index extendsreachwith its own jump. For[3, 2, 1, 0, 4], index 4 would setreach = 8, the check would pass, and the function would return True instead of False.- What are the time and space complexity?
- In Jump Game II (LC 45), why not count every time
fargrows? A jump is counted when
ireachesend, the last index the current number of jumps can cover. Thenendbecomesfar. Counting every growth offarcounts growths that happen inside one jump. For[1, 2, 2, 1],fargrows three times, at index 0, 1 and 2, but the answer is 2.
SWE Reasoning
Spot it
- Each step offers a choice, such as how far to jump, where to start or where to cut.
- You can argue that one choice keeps every option the other choices would keep.
- The question asks whether something is possible, or for a minimum or maximum count, and not for the path itself.
- A search over all choices is far too slow, but one pass over the input in a fixed order looks enough.
- A small input where the best choice now blocks a better one later does not exist, or you can explain why.
The invariant, step by step
reach = 0. Only index 0 can be stood on, before any jump.- At index
i, the checki > reachruns first. If it is true, no jump lands oni, and the function returns False. - Otherwise
ican be stood on. Its jumps can land anywhere ini + 1..i + nums[i]. reach = max(reach, i + nums[i])joins that range to the block. The larger value contains every index of the smaller one.- The block
0..reachtherefore holds exactly the indices that some run of jumps can land on. - If the loop stands on every index, the last index is in the block, and the function returns True.
Traps
- Updating
reachbefore the check. An index pastreachmust not extend it. For[3, 2, 1, 0, 4]the wrong order returns True and the right answer is False. range(len(nums) - 1). The last index is never checked, so the same input returns True.reach = i + nums[i]withoutmax. A short jump after a long one lowersreach. For[4, 1, 0, 0, 0]the loop stops early and returns False instead of True.- Using greedy where the exchange fails. In House Robber (LC 198), the richest house is not always in the best answer.
- Stating the choice without the proof. "Take the biggest" is not an argument. Say what the greedy choice keeps that the other choices also keep.