You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 105We're going to derive the solution from scratch — not just memorize the loop. By the end, you'll understand why tracking a single variable works, why greedy beats DP here, and how to spot the same pattern in other reachability problems.
You start at index 0. At each position i, the number nums[i] tells you the maximum distance you can leap forward — but you can choose any smaller jump too. You want to know: can I land on the last index?
Let's think about what makes this possible or impossible:
Forward view: From where I am, how far can I reach? At each step, expand my "reachable frontier." If it ever falls short of a position I need to reach → stuck.
Backward view: Starting from the last index, work backwards. Which positions can jump to a position that's already "good"? If index 0 is good → success.
The forward view is simpler — and that's the greedy approach.
Concrete examples:
Example 1: [2, 3, 1, 1, 4] — starting with 2 at index 0, you can reach indices 1 and 2. From index 1 (value 3), you can reach all the way to index 4 (the end). ✅ Reachable.
Example 2: [3, 2, 1, 0, 4] — from index 0 (3) you can reach up to index 3. But at index 3, the value is 0 — you can't move further. No matter which path you take, you get trapped at index 3. ❌ Unreachable.
You don't need to plan a full path. You just need to know: as you scan left to right, is there any point where the furthest reachable index falls behind your current position?
If maxReach < i at any point → you're stuck. Otherwise, keep going and update maxReach = max(maxReach, i + nums[i]).
Define maxReach = the furthest index you can reach so far.
Break this down:
maxReach) is behind the position you're at (i), you physically cannot be at position i. Game over.i, you can jump up to i + nums[i]. Update maxReach if this extends your frontier.maxReach ≥ last_index.)At each step, you take the locally optimal action: jump as far as you can from wherever you are. But unlike many greedy problems, there's no tradeoff — reaching further can never hurt you. Here's why:
j, you can also reach every index between your current position and j (just take smaller jumps).i, you create a continuous reachable interval [i, i+nums[i]].[0, maxReach] — a single contiguous block from the start.maxReach only grows, there's never a reason to be "strategic" about which position to jump to — farther is always better.This monotonicity is what makes greedy optimal. If jumps were exact (not "up to"), or if there were costs, greedy would fail — and that's when DP takes over.
maxReach. We don't need to try every path (O(2ⁿ)) or build a DP array of reachable positions (O(n²·m)). One scan, one variable — O(n) time, O(1) space.
Choose an example and step through the greedy scan:
The key property that makes greedy correct here is monotonicity of reachability.
Claim: After processing positions [0..i], the set of reachable positions is exactly [0..maxReach] — a single contiguous prefix.
Base case (i=0): You can reach [0, nums[0]] — a contiguous segment from 0.
Inductive step: Assume after processing [0..i-1], reachable = [0..R] where R = maxReach. At position i:
i > R: position i is unreachable → we're stuck.i ≤ R: we can be at i, and from i we can reach up to i + nums[i]. So the new reachable set is [0..max(R, i + nums[i])] — still a contiguous prefix.This invariant proves: maxReach is sufficient to track everything. No DP needed.
maxReach alone doesn't work. You need to track "when does the current jump's range end?" — which adds a second state variable. Even then, it's still greedy, but the decision is more subtle.
maxReachdp[i] = "is i reachable?"There's a third approach that's also O(n) — scanning right to left:
Define lastGood = the rightmost index we know can reach the end. Initially, lastGood = n - 1 (the last index can trivially reach itself).
Scan from right to left. At position i, ask: can I jump from i to anywhere ≥ lastGood? If i + nums[i] ≥ lastGood, then i is also "good" — set lastGood = i.
At the end: if lastGood === 0 → we can reach the end from the start.
| Problem | Core Idea | Pattern |
|---|---|---|
| Jump Game | maxReach = max(maxReach, i + nums[i]) |
Reachability frontier |
| Jump Game II | maxReach + currentEnd + jumps counter |
Reachability + level-order BFS in 1D |
| Can Place Flowers | greedy place if no adjacent conflict |
Local optimal = global optimal |
| Gas Station | track surplus, reset when negative |
Contiguous segment with maintenance of invariant |
| Video Stitching / Min Taps to Water Garden | maxReach from current coverage window |
Interval coverage + greedy frontier |
The common thread: a monotonically expanding frontier where "further is always better." When you spot that property, greedy is on the table — and it's usually the optimal answer.
maxReach. For Jump Game II (minimum jumps), you need maxReach + currentEnd + jumps. The complexity of the state tells you whether it's simple greedy or layered greedy.maxReach ≥ lastIndex, return true. As soon as i > maxReach, return false. These early exits often speed up real-world performance dramatically on sparse inputs.Let me start with a genuine compliment: you understand the greedy approach correctly. The structure — stuck check, reach expansion, early exit — is exactly right. You're tracking max_reach as the frontier and using enumerate() for clean iteration. The max_reach < idx stuck check is in the right place. This is the right algorithm — it's just two fragile mistakes in the numbers.
max_reach >= len(nums) is an off-by-one error BLOCKINGThe last index of an array of length n is n - 1, not n. By comparing against len(nums) instead of len(nums) - 1, your early exit never fires when the answer is True — because max_reach can never exceed the array bounds. When max_reach == n - 1 (exactly at the last index), the condition max_reach >= n is False, so it keeps scanning — and eventually hits the return False fallback.
Counterexample: [2, 3, 1, 1, 4] — the main LeetCode example. Expected: True. Your code: False.
| idx | num | max_reach (before) | stuck? (max_reach < idx) |
early exit? (max_reach >= 5) |
max_reach (after) |
|---|---|---|---|---|---|
| 0 | 2 | 0 | No (0≥0) | No (0<5) | 2 |
| 1 | 3 | 2 | No (2≥1) | No (2<5) | 4 |
| 2 | 1 | 4 | No (4≥2) | No (4<5) ← SHOULD BE TRUE! | 4 |
| 3 | 1 | 4 | No | No (4<5) | 4 |
| 4 | 4 | 4 | No | No (4<5) | 8 |
| loop end | — | — | — | — | return False ← WRONG |
At idx=1, max_reach becomes 4, which equals len(nums) - 1 = 4. The last index is reachable! But because your check tests max_reach >= 5, it misses this. The code runs to completion and returns False.
⚠️ This bug always fires for valid inputs where max_reach lands exactly on the last index. It's not an edge case — it's the normal case for the problem's own example.
if max_reach >= len(nums) - 1: return True
The last valid index is n-1. When max_reach covers it, you're done.
return False at the end is logically backwards BLOCKINGEven after fixing Bug #1, this bug would still bite on the single-element case. Consider [0] (n=1):
| idx | num | max_reach (before) | stuck? | early exit? (max_reach >= 0) |
max_reach (after) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | No | Yes! (0≥0) | — |
With Bug #1 fixed, the single-element case would work. But conceptually, the return False is wrong. Think about what it means for the loop to complete without returning:
max_reach < idx) never fired → we were never stuck at any position.max_reach >= n - 1) never fired → max_reach never covered the last index.But if we processed every index without getting stuck, that means we visited every position including the last one. By definition, the last index is reachable. The correct fallback after a complete scan is return True.
⚠️ In practice, with Bug #1 fixed and the early exit working, this return False would only be hit on edge cases where the early exit somehow never fires despite reaching the end. But semantically return True is the correct invariant, and writing return False signals to any reviewer that you haven't thought through what "loop completed" actually means.
return True — if we scanned the whole array without getting stuck, the last index is reachable.
max_reach = 0 is followed by 8 trailing spaces before the newline. Then there's a blank line before the for loop. This is minor, but in FAANG interviews, clean formatting is a baseline expectation — it tells the interviewer you're careful. The fix: one blank line between logical blocks (initialization → loop) with no trailing whitespace.
Your early-exit check (max_reach >= len(nums)) happens before the max() update. This means if the current position's jump extends reach to the end, you won't catch it until the next iteration — wasting a loop cycle. It's not a correctness bug, but it's a minor inefficiency and a sign you haven't fully traced the control flow.
With your order, for [2,3,1,1,4]: at idx=1, max_reach updates to 4. But you already checked 2 ≥ 5 earlier in the iteration. So you need idx=2 to check 4 ≥ 5 — still fails. It doesn't matter here because your condition is wrong anyway, but with the correct condition it would add one unnecessary iteration. Move the check after the update.
return False is the opposite of what the loop-invariant saysAfter a complete scan without hitting the stuck check, you've proven every position from 0 to n-1 is reachable. The loop-invariant: "after processing i, all positions ≤ max_reach are reachable." If the loop completes, max_reach ≥ n-1 (otherwise the stuck check would have fired at some point). The return value must be True. Writing return False contradicts the invariant you just maintained.
This is exactly the kind of thing a FAANG interviewer would ask: "Walk me through a case that hits that final return. What does it mean when the loop finishes normally?" If you can't answer that, or realize it should never happen, the return False becomes a red flag.
len(nums) - 1 instead of len(nums)return True at the end — loop completion means we visited every index without getting stuckmax() update, so we can exit in the same iterationOr the even more concise version (same correctness):
You have the algorithm. You understand the greedy insight. The stuck-check / reach-expansion / early-exit structure is exactly what a FAANG interviewer wants to see. This is a "getting warmer" submission — the thinking is correct, the implementation has two small but fatal number-errors.
But in a real interview, these bugs would sink you. Here's why — and how to catch them before the interviewer does:
n - 1, not n. Always. Whenever you write len(nums) in a comparison, pause and ask: "Am I comparing against the length or the last index?" If it's the latter, subtract 1.[2,3,1,1,4] through your code. At idx=1, max_reach becomes 4, and n=5. 4 ≥ 4? The check should return True — but it doesn't. Tracing catches the off-by-one instantly.return should tell a story. You have three returns:
return False when stuck → correct
return True on early exit → correct intent
return False at the end → "loop finished and... we failed?"
Bottom line: You're 10 characters away from the optimal solution. - 1 on the comparison and True on the fallback — that's it. The algorithm is right. Now make the numbers right.