Jump Game (Greedy)
A medium Greedy interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Greedy
- Sheets
- 2
- Core for
- 3 roles
The problem
You are given a non-negative integer array where each element represents your maximum jump length from that position. Determine if you can reach the last index starting from the first position.
Example 1
- Input
- nums = [2,3,0,1,4]
- Output
- true
- Why
- Jump 1 to index 1 (value 3), then 3 to index 4 (end).
Example 2
- Input
- nums = [2,0,1,0,1]
- Output
- false
- Why
- From index 0 (value 2) you can reach index 1 (value 0) or index 2 (value 1). Index 1 is stuck at 0. From index 2 you can only reach index 3 (value 0), also stuck. The last index is unreachable.
Constraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-29Stop thinking about which jumps to take. The only thing that decides the answer is the furthest index anything can reach so far, and that is a single number you can carry left to right. If you ever arrive at an index that is past it, no sequence of jumps could have put you there, so the answer is already no.
Approaches, worst first
Try every jump
time O(2^n) · space O(n)
From each index, branch into every landing spot it can reach and recurse. It is the definition of the problem written as code, which is why it is the one everybody writes first, and it re-explores the same suffix through thousands of different prefixes.
Reachability table
time O(n^2) · space O(n)
reach[i] is true when some earlier index that is itself reachable can jump to i. Fills left to right and kills the repeated work, but every cell still scans backwards over the whole prefix looking for one witness.
One greedy sweepWrite this one
time O(n) · space O(1)
Keep `furthest`, the largest index reached so far. Walk i from 0; bail out the moment i > furthest, otherwise raise furthest to max(furthest, i + nums[i]). You never need the table, because a prefix is either fully reachable or the walk has already stopped.
Where people lose marks · 4
- A 0 is not automatically fatal. It only ends the run when nothing before it jumps over it, which is exactly what comparing i against furthest tests for you.
- A single-element array is already standing on the last index, so the answer is true; an implementation that starts by looking for a jump reports false.
- Compare i > furthest BEFORE using nums[i]. Checking after it means you have already read a cell you never legally stood on.
- furthest can run past the end of the array. That is fine and you should not clamp it; overshooting the last index is what success looks like.
The theory behind it
Greedy — the ground this problem stands on. All Greedy problems
What Greedy is
A greedy algorithm makes the best-looking choice available right now, at every step, without ever looking back or second-guessing its decision. Think of a cashier making change by handing over the largest possible coin first, repeatedly, until the total is reached. Unlike dynamic programming, which saves and compares answers to multiple overlapping paths, a greedy strategy commits to one immediate option and keeps moving forward.
When to reach for it
Reach for greedy when problems ask for minimum jumps, interval scheduling, assigning resources to maximize satisfaction, or finding fractional values. Key signals include sorted orders where greedily taking the next item never hurts future options, or gas station round trips where running balances prove reachability. If you can prove that taking the immediate best choice never leaves you worse off than any alternative, greedy gives the fastest answer.
How the pattern works
Start by sorting the input to bring the most promising candidates to the front. At each position, evaluate your local rule, take the best available piece, and update your running state. The crucial mental step is proving the greedy choice property: demonstrate that picking this immediate winner cannot block a better global solution down the road. If choosing an item now forces you to reconsider past decisions when conditions change later, greedy fails and you must switch to dynamic programming instead.
More Greedy problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .