Jump Game (LeetCode 55)
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.
Worked Examples
nums = [2,3,1,1,4]true3 carries you straight to index 4, the last index. Other routes work too; one is enough.nums = [3,2,1,0,4]false0 + 3, 1 + 2, 2 + 1), and index 3 holds 0, so no jump ever passes it. Index 4 stays out of reach.⚖️Formal Constraints & Bounds
1 <= nums.length <= 1040 <= nums[i] <= 105
Core Insight
You never need the path, only how far any path can get: the reachable indices always form one block 0..reach, so one number and one pass decide the answer.
Real-World Scenario & Production Applications
Any chain of forward hops with a limited range per hop: relay stations along a pipeline, charging stops for a drone, stepping stones on a path. Whether the end can be reached never needs the full route, only the furthest point any route could reach so far, so one running number answers it in a single pass.
Step-by-Step Execution Trace Table
Example 2, nums = [3,2,1,0,4] (the trap case):
i | nums[i] | Check i > reach | reach = max(reach, i + nums[i]) | What it means |
|---|---|---|---|---|
| 0 | 3 | 0 > 0: no | max(0, 0 + 3) = 3 | Indices 0 to 3 can be landed on |
| 1 | 2 | 1 > 3: no | max(3, 1 + 2) = 3 | No further than before |
| 2 | 1 | 2 > 3: no | max(3, 2 + 1) = 3 | No further than before |
| 3 | 0 | 3 > 3: no | max(3, 3 + 0) = 3 | Index 3 can't move on |
| 4 | 4 | 4 > 3: yes | (not reached) | No jump lands on index 4: return False |
| 1 | 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. |
| 2 | Every index from `0` to `reach` can be landed on (a jump may be shorter than `nums[i]`), so extend it with `reach = max(reach, i + nums[i])`: the larger reach keeps every option. |
| 3 | Start `reach = 0`, loop `for i in range(len(nums))` once, and `return True` after the loop. |
| 4 | The trap: check `if i > reach: return False` before reading `nums[i]`, or an index nobody can land on extends `reach`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A path search looks necessary here: from index 0 you could jump 1, 2, ... up to nums[0] steps, and every landing spot branches again. Greedy skips the search. A jump may be shorter than its maximum, so if some jump can land on index k, every index before k can be landed on too. The reachable indices are therefore always one unbroken block 0..reach, and a single number, reach, says everything about the past. Walk the array once, and at each index you can stand on, push reach out to i + nums[i] if that is further.
🪜 The Analogy: Stepping Stones Across a River
You cross a river on a row of stepping stones. Each stone has a number painted on it: how many stones ahead you can leap from there, at most. You don't plan a route. You walk along the stones you can reach and keep one note in your head: "the furthest stone I could get to so far." Each new stone may move that note further. If you ever look at a stone beyond the note, nobody can stand on it, and the far bank is out of reach.
🔑 Why It Works
This is the greedy argument in one line: max keeps the larger block, and a larger block contains every index a smaller one does, so choosing it can never cost an option. A locally best choice that never has to be undone is exactly when greedy is correct. The order of the two lines matters: check i > reach first, so an index nobody can land on never extends reach.
Extending
reachfrom an index you can't stand on: checki > reachbeforereach = max(reach, i + nums[i]). On[3,2,1,0,4]index 4 is pastreach = 3; letting its jump count returnsTrueinstead ofFalse.Assigning instead of taking the max:
reach = i + nums[i]lets a short jump after a long one shrink the reach, so[4,1,0,0,0]gets stuck at index 3 and returnsFalseinstead ofTrue.Searching paths: trying every jump length from every index is correct but costs up to O(N · max(nums[i])), about 10^9 steps at these limits. One number,
reach, replaces the whole search.Answering a different question:
reachonly says yes or no. The fewest jumps, as in Jump Game II (LC 45), needs a second boundary for where the current jump runs out.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The longest jump from each index" and "can you reach the last index": a yes/no reachability question where a longer jump is never worse than a shorter one. When the locally best option (the furthest reach) keeps every choice any other option keeps, that is the signal for Greedy.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule at each index i: if i > reach, return False; otherwise reach = max(reach, i + nums[i]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Greedy. I never need the actual path, only the furthest index any sequence of jumps could land on so far; I call it reach. A jump can be shorter than its maximum, so every index up to reach can be landed on, and the reachable indices always form one block from zero to reach. I walk the array once. At each index I first check whether i is past reach: if it is, nobody can stand there, so I return false. Otherwise I extend reach to the max of reach and i plus nums of i. Taking the max never loses an option, because a longer block contains every shorter one. The trap is the order: checking first stops an unreachable index from pushing reach forward. If the loop finishes, I return true. One pass, so
O(N)time andO(1)space.
Complexity & Mathematical Proof
O(N)
Look at the code: reach = 0 is one assignment, and for i in range(len(nums)) visits each index at most once. Its body does one comparison (i > reach) and one max, a constant amount of work, and the loop may stop early at return False. Total: O(N).
O(1)
The code keeps only reach and i, whatever the input size, and returns one boolean: O(1) extra space.
T(N) = O(1) + N · O(1) = O(N)
Derivation Progression
O(1)
reach = 0 is one assignment.
at most N iterations
for i in range(len(nums)) visits each index once, and stops early if return False runs.
O(1) per iteration
One comparison i > reach and one max(reach, i + nums[i]), whatever N is.
O(N)
Constant work per index over at most N indices.
Variable Definitions
Number of indices, len(nums)
Furthest index some run of jumps can land on so far
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): reach, i
O(1): one boolean
Boundary Best / Worst Cases
: nums[0] = 0 with more than one index, so the loop returns False at i = 1
: the last index is reachable, so every index is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the longest jump allowed from each index", "can you reach the last index". A yes/no reachability question where a longer jump is never worse than a shorter one: Greedy with one running number, reach.
indices and jumps up to . Trying every jump length from every index costs up to steps; the greedy reach is time and space, and it reads nums once, left to right, so it also works on a stream.
On a stream, a record that arrives beyond the covered prefix must wait: it can't move the prefix forward until the gap before it is filled. i + nums[i] is at most , so it fits a 32-bit integer with room to spare.
Core Algorithmic State Invariants
- Why "At Most" Makes One Number Enough
If every jump had to be exactly nums[i] long, the reachable indices could have holes, and one number could not describe them: you would need a set of indices or a table. Because a jump may be shorter, the reachable indices have no holes, and reach alone says everything.
TrueAfter the Loop Needs No Extra Test
The loop only finishes when no index failed i > reach, the last index included, so return True needs no check such as reach >= len(nums) - 1.
- A Zero Is a Wall Only If Nothing Jumps Over It
nums[i] == 0 stops the walk only when reach == i at that moment. Any earlier index that jumps past it keeps reach beyond it, as in [2,0,0], where index 0 already reaches the last index.
Jump Game (LeetCode 55)
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.
Worked Examples
nums = [2,3,1,1,4]true3 carries you straight to index 4, the last index. Other routes work too; one is enough.nums = [3,2,1,0,4]false0 + 3, 1 + 2, 2 + 1), and index 3 holds 0, so no jump ever passes it. Index 4 stays out of reach.⚖️Formal Constraints & Bounds
1 <= nums.length <= 1040 <= nums[i] <= 105
Core Insight
You never need the path, only how far any path can get: the reachable indices always form one block 0..reach, so one number and one pass decide the answer.
Real-World Scenario & Production Applications
Any chain of forward hops with a limited range per hop: relay stations along a pipeline, charging stops for a drone, stepping stones on a path. Whether the end can be reached never needs the full route, only the furthest point any route could reach so far, so one running number answers it in a single pass.
Step-by-Step Execution Trace Table
Example 2, nums = [3,2,1,0,4] (the trap case):
i | nums[i] | Check i > reach | reach = max(reach, i + nums[i]) | What it means |
|---|---|---|---|---|
| 0 | 3 | 0 > 0: no | max(0, 0 + 3) = 3 | Indices 0 to 3 can be landed on |
| 1 | 2 | 1 > 3: no | max(3, 1 + 2) = 3 | No further than before |
| 2 | 1 | 2 > 3: no | max(3, 2 + 1) = 3 | No further than before |
| 3 | 0 | 3 > 3: no | max(3, 3 + 0) = 3 | Index 3 can't move on |
| 4 | 4 | 4 > 3: yes | (not reached) | No jump lands on index 4: return False |
| 1 | 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. |
| 2 | Every index from `0` to `reach` can be landed on (a jump may be shorter than `nums[i]`), so extend it with `reach = max(reach, i + nums[i])`: the larger reach keeps every option. |
| 3 | Start `reach = 0`, loop `for i in range(len(nums))` once, and `return True` after the loop. |
| 4 | The trap: check `if i > reach: return False` before reading `nums[i]`, or an index nobody can land on extends `reach`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A path search looks necessary here: from index 0 you could jump 1, 2, ... up to nums[0] steps, and every landing spot branches again. Greedy skips the search. A jump may be shorter than its maximum, so if some jump can land on index k, every index before k can be landed on too. The reachable indices are therefore always one unbroken block 0..reach, and a single number, reach, says everything about the past. Walk the array once, and at each index you can stand on, push reach out to i + nums[i] if that is further.
🪜 The Analogy: Stepping Stones Across a River
You cross a river on a row of stepping stones. Each stone has a number painted on it: how many stones ahead you can leap from there, at most. You don't plan a route. You walk along the stones you can reach and keep one note in your head: "the furthest stone I could get to so far." Each new stone may move that note further. If you ever look at a stone beyond the note, nobody can stand on it, and the far bank is out of reach.
🔑 Why It Works
This is the greedy argument in one line: max keeps the larger block, and a larger block contains every index a smaller one does, so choosing it can never cost an option. A locally best choice that never has to be undone is exactly when greedy is correct. The order of the two lines matters: check i > reach first, so an index nobody can land on never extends reach.
Extending
reachfrom an index you can't stand on: checki > reachbeforereach = max(reach, i + nums[i]). On[3,2,1,0,4]index 4 is pastreach = 3; letting its jump count returnsTrueinstead ofFalse.Assigning instead of taking the max:
reach = i + nums[i]lets a short jump after a long one shrink the reach, so[4,1,0,0,0]gets stuck at index 3 and returnsFalseinstead ofTrue.Searching paths: trying every jump length from every index is correct but costs up to O(N · max(nums[i])), about 10^9 steps at these limits. One number,
reach, replaces the whole search.Answering a different question:
reachonly says yes or no. The fewest jumps, as in Jump Game II (LC 45), needs a second boundary for where the current jump runs out.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The longest jump from each index" and "can you reach the last index": a yes/no reachability question where a longer jump is never worse than a shorter one. When the locally best option (the furthest reach) keeps every choice any other option keeps, that is the signal for Greedy.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule at each index i: if i > reach, return False; otherwise reach = max(reach, i + nums[i]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Greedy. I never need the actual path, only the furthest index any sequence of jumps could land on so far; I call it reach. A jump can be shorter than its maximum, so every index up to reach can be landed on, and the reachable indices always form one block from zero to reach. I walk the array once. At each index I first check whether i is past reach: if it is, nobody can stand there, so I return false. Otherwise I extend reach to the max of reach and i plus nums of i. Taking the max never loses an option, because a longer block contains every shorter one. The trap is the order: checking first stops an unreachable index from pushing reach forward. If the loop finishes, I return true. One pass, so
O(N)time andO(1)space.
Complexity & Mathematical Proof
O(N)
Look at the code: reach = 0 is one assignment, and for i in range(len(nums)) visits each index at most once. Its body does one comparison (i > reach) and one max, a constant amount of work, and the loop may stop early at return False. Total: O(N).
O(1)
The code keeps only reach and i, whatever the input size, and returns one boolean: O(1) extra space.
T(N) = O(1) + N · O(1) = O(N)
Derivation Progression
O(1)
reach = 0 is one assignment.
at most N iterations
for i in range(len(nums)) visits each index once, and stops early if return False runs.
O(1) per iteration
One comparison i > reach and one max(reach, i + nums[i]), whatever N is.
O(N)
Constant work per index over at most N indices.
Variable Definitions
Number of indices, len(nums)
Furthest index some run of jumps can land on so far
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(1): reach, i
O(1): one boolean
Boundary Best / Worst Cases
: nums[0] = 0 with more than one index, so the loop returns False at i = 1
: the last index is reachable, so every index is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the longest jump allowed from each index", "can you reach the last index". A yes/no reachability question where a longer jump is never worse than a shorter one: Greedy with one running number, reach.
indices and jumps up to . Trying every jump length from every index costs up to steps; the greedy reach is time and space, and it reads nums once, left to right, so it also works on a stream.
On a stream, a record that arrives beyond the covered prefix must wait: it can't move the prefix forward until the gap before it is filled. i + nums[i] is at most , so it fits a 32-bit integer with room to spare.
Core Algorithmic State Invariants
- Why "At Most" Makes One Number Enough
If every jump had to be exactly nums[i] long, the reachable indices could have holes, and one number could not describe them: you would need a set of indices or a table. Because a jump may be shorter, the reachable indices have no holes, and reach alone says everything.
TrueAfter the Loop Needs No Extra Test
The loop only finishes when no index failed i > reach, the last index included, so return True needs no check such as reach >= len(nums) - 1.
- A Zero Is a Wall Only If Nothing Jumps Over It
nums[i] == 0 stops the walk only when reach == i at that moment. Any earlier index that jumps past it keeps reach beyond it, as in [2,0,0], where index 0 already reaches the last index.