Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Each value is the max jump length from that index; decide whether you can reach the last index. The DP answer marks which indices are 'good' (can reach the end) in O(n²). The optimal greedy does it in one pass: track the farthest index reachable so far, and if you ever stand on an index beyond that reach, you're stuck. O(n) time, O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that this feasibility question doesn't need a path or a full DP — that a single greedy 'farthest reachable' frontier captures everything — and whether you can argue why the greedy is correct, not just that it passes.
Where candidates slip
Over-engineering with O(n²) DP or recursion that TLEs, or in the greedy version checking i > farthest in the wrong place (after updating) so a stranded index slips through.
How to stand out
Present the DP first to show you can model it, then collapse to the O(n) greedy and justify it: a contiguous reachable prefix means the only thing that can stop you is the frontier failing to advance past your current position.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCan you reach the last index?Need a full model or just yes/no?Model it / deriveOptimalExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Dynamic Programming — Mark the 'Good' Indices
1Hint 1Explore hintHide hint
Call an index 'good' if you can reach the last index from it. The last index is trivially good — work backward from there.
2Hint 2Explore hintHide hint
Index i is good if some j in [i+1, i+nums[i]] is already known to be good. How would you check that?
3Hint 3Explore hintHide hint
Fill a boolean dp array right to left; for each i scan its reachable range for any good index. Answer is dp[0].
A · Core idea
Define dp[i] = true if the last index is reachable starting from i. The last index is good by definition. Process indices from right to left; i is good if any index within its jump range [i+1, i+nums[i]] is already marked good.
Why work right to left. Reachability composes backward: 'can I finish from i?' depends on whether I can hop to some position that itself can finish. By filling from the end, every index in i's reach has already been decided, so the lookup is a simple scan over a settled region.
Why scan the whole reachable range. From i you may land on any index up to i + nums[i]. If even one of those is good, then i is good — you'd jump there and let it carry you home. So we OR together the goodness of the reachable window. The moment we find a good target we can stop scanning that window.
Why we don't ship this. That inner scan over each index's range is what makes it quadratic. For n = 10⁴ that's up to 10⁸ checks — borderline and wasteful when the structure is so simple. The DP is a great way to prove the recurrence and to convince yourself reachability is well-defined, but the next observation collapses all that scanning into a single number.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [2, 3, 1, 1, 4]dp[4]
last index — good by definition
dp = [_,_,_,_,T]trueC · Code with teaching comments
Reference implementation previewpublic boolean canJump(int[] nums) { int n = nums.length; boolean[] dp = new boolean[n]; dp[n - 1] = true; for (int i = n - 2; i >= 0; i--) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The DP exposes the key fact the greedy will exploit: goodness only ever propagates backward from a contiguous good region near the end. Once you notice the good indices form a single growing suffix-frontier (not scattered islands), you realise you never needed an array of booleans — just the boundary of that frontier.
ComplexityO(n²) time, O(n) space — For each of the n indices we may scan up to its full jump range looking for a good index, so the worst case is O(n²) time; the boolean dp array uses O(n) space.
E · Edge cases and pitfalls5nums = [0] — n=1 so dp[0] is set true by the base case and the loop never runs → returns true.Explore edge casesHide edge cases
Edge cases handled
nums = [0]n=1 so dp[0] is set true by the base case and the loop never runs → returns true.nums = [3, 2, 1, 0, 4]dp[3]'s only reach is index 3+0=3 (itself); it stays false, and that falseness propagates back to dp[0] → false.
Pitfalls
- Forgetting to clamp i + nums[i] to n-1 — out-of-bounds on large jump values.
- Filling dp left to right — you'd read undecided cells.
- Shipping the O(n²) version when n = 10⁴ makes the greedy clearly preferable.
Approach 2 of 2 · Optimal
Greedy — Track the Farthest Reachable Index (Optimal)
1Hint 1Explore hintHide hint
Instead of asking 'is each index good?', ask one running question: what's the farthest index I can possibly reach so far?
2Hint 2Explore hintHide hint
Sweep left to right. If you ever arrive at an index i that's beyond your current farthest reach, no jump sequence could have put you there — fail.
3Hint 3Explore hintHide hint
Otherwise extend the frontier: farthest = max(farthest, i + nums[i]). If you finish the sweep (or farthest covers the end), you succeed.
A · Core idea
Maintain farthest = the largest index reachable using all the jumps considered so far. Scan left to right. At index i, if i > farthest you could never have stepped onto i, so return false. Otherwise extend the frontier with farthest = max(farthest, i + nums[i]). Survive the whole scan and you can reach the end.
Why one number captures everything. From index i you can land on any index up to i + nums[i] — a contiguous block, not a scattered set. That means the set of all reachable indices is itself always a contiguous prefix [0, farthest]; there are never gaps. So 'which exact indices are reachable' is fully described by a single boundary, farthest. We don't need a boolean array or a path — just the right edge of the reachable interval.
Why `i > farthest` is the only failure mode. As long as i <= farthest, index i lies inside the reachable prefix, so we genuinely can stand there, and from there we get to push the frontier further. The only way to fail is to reach an i that the frontier hasn't covered — meaning every earlier index's reach died out before i, the classic 'trapped behind a 0' situation. Detecting that one condition is the entire algorithm.
Why the greedy is provably correct, not just lucky. Because the reachable region is a contiguous prefix, extending farthest greedily at every reachable index can never miss an option: any index we could reach, we do account for, since its whole jump range is within [i+1, i+nums[i]] and i is already inside the frontier. There's no future decision that a different earlier choice would have unlocked — the maximum frontier dominates all alternatives. That domination argument is what turns a heuristic into a correct greedy.
Why this beats the DP outright. The DP rediscovers reachability by scanning each index's range; the greedy folds all of that into a single running maximum, dropping O(n²) to O(n) and O(n) space to O(1). Same answer, none of the bookkeeping.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 2, 1, 0, 4]Array state
i=0
farthest jumps to 3
falseC · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The mental shift is from 'compute goodness for every index' to 'maintain the right edge of where I can be'. Once you see that 'jump up to k' makes the reachable set a gap-free interval, the whole problem reduces to: does the right edge of that interval ever fall behind my cursor? One variable, one inequality, done. This frontier idea is the seed for Jump Game II (advance the frontier level by level to count jumps).
ComplexityO(n) time, O(1) space — A single left-to-right pass with O(1) work per element (one comparison, one max) gives O(n) time, and we keep just one integer farthest, so O(1) space.
E · Edge cases and pitfalls5nums = [0] — i=0 with i (0) not > farthest (0); farthest >= last (0) → returns true immediately.Explore edge casesHide edge cases
Edge cases handled
nums = [0]i=0 with i (0) not > farthest (0); farthest >= last (0) → returns true immediately.nums = [2, 0, 0]i=0 sets farthest=2 ≥ last → true, even though indices 1 and 2 hold zeros (we jump over them).
Pitfalls
- Updating farthest BEFORE the i > farthest check — lets a stranded index slip through.
- Comparing i + nums[i] without keeping the running max — a later small jump shouldn't shrink the frontier.
- Forgetting nums[i] can be 0 — a 0 only fails when it's the frontier's edge and the cursor catches up.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean canJump(int[] nums) { int farthest = 0; for (int i = 0; i < nums.length; i++) { if (i > farthest) return false; farthest = Math.max(farthest, i + nums[i]);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Exponential backtracking
Recursively trying every jump length from every index revisits the same positions and blows up exponentially, timing out on n = 10⁴.
Explore the code comparisonHide the code comparison
Exponential backtracking
Recursively trying every jump length from every index revisits the same positions and blows up exponentially, timing out on n = 10⁴.
Don't write this
boolean canJumpFrom(int[] nums, int pos) {
if (pos >= nums.length - 1) return true;
for (int step = 1; step <= nums[pos]; step++)
if (canJumpFrom(nums, pos + step)) return true; // O(2^n)
return false;
}Write this instead
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farthest) return false;
farthest = Math.max(farthest, i + nums[i]);
}
return true;2Check order inverted in the greedy
Updating farthest before testing i > farthest hides the stranded case — you might extend the frontier using an index you can't actually stand on.
Explore the code comparisonHide the code comparison
Check order inverted in the greedy
Updating farthest before testing i > farthest hides the stranded case — you might extend the frontier using an index you can't actually stand on.
Don't write this
farthest = 0
for i, x in enumerate(nums):
farthest = max(farthest, i + x) # updated too early
if i > farthest: # now unreachable indices are masked
return False
return TrueWrite this instead
farthest = 0
for i, x in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + x)
return True3Letting a small jump shrink the frontier
Assigning farthest = i + nums[i] without the max can pull the horizon backward when a later index has a small value, falsely reporting failure.
Explore the code comparisonHide the code comparison
Letting a small jump shrink the frontier
Assigning farthest = i + nums[i] without the max can pull the horizon backward when a later index has a small value, falsely reporting failure.
Don't write this
farthest = i + nums[i]; // overwrites — loses a bigger earlier reachWrite this instead
farthest = Math.max(farthest, i + nums[i]);Revise
Carry the pattern into the interview
Pattern to remember
Greedy reachability — track farthest reachable index
Code pattern to memorize
farthest = 0
for i, x in enumerate(nums):
if i > farthest: return False # stranded before reaching i
farthest = max(farthest, i + x)
return TrueRules to remember
- 1Carry a single number `farthest` = the maximum index reachable using everything seen so far.
- 2Before processing index
i, if `i > farthest` you can never stand oni→ returnFalseimmediately. - 3At each reachable
i, update `farthest = max(farthest, i + nums[i])` — the new horizon. - 4You don't need to track exact jump sequences — only the frontier of reachability matters, which is why greedy beats DP here.
- 5Early-out the moment
farthest >= n - 1if you like; reaching the end means success regardless of what's after.
Use this pattern when
- Reachability / feasibility on a line where each position grants a forward range
- You only need yes/no (or a min count), not the actual path taken
- A local 'how far can I get' frontier can be extended greedily left to right
- Each step's options are a contiguous prefix of future indices (a jump *up to* k)
Choose another pattern when
- You must return the actual jump path → augment with parent pointers, not bare greedy
- Jumps can go backward or costs vary per edge → model as a graph + BFS/Dijkstra
- Minimum number of jumps with non-uniform structure → Jump Game II (still greedy, but level-by-level)
- Ranges aren't contiguous prefixes (arbitrary reachable sets) → general graph reachability
Interview takeaway
Jump Game is the cleanest 'reachability frontier' greedy: one variable, one pass, and the key realisation that you never need the route — only whether the horizon ever falls behind you. The same farthest-reach trick scales to Jump Game II (count jumps) and Gas Station (circular feasibility).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical reachability-frontier greedy — collapse 'is each position good?' into one running 'farthest reachable index' and fail only when the cursor overtakes the frontier. Recognise it for line-walking feasibility questions; it generalises to Jump Game II (count jumps) and shares its frontier-and-reset spirit with Gas Station.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Jump Game IIMinimum jumps — same frontier, but advance level by level (BFS-style) counting each expansion.
- Jump Game IIIComing soonJumps go i±nums[i] to a zero — reachability becomes a graph BFS/DFS, not a linear frontier.
- Jump Game VIComing soonMax score with a window of jumps — sliding-window maximum (monotonic deque) over a DP.
- Gas StationCircular feasibility with the same 'track a running frontier and reset' greedy flavour.