Jump Game
Problem Statement
You are given an integer array nums. You start at index 0, and nums[i] tells you the maximum jump length you may take from index i. Return true if you can reach the last index, otherwise return false.
Input
An integer array nums, where each value is the maximum jump length from that index.
Output
A boolean: true if the final index is reachable from index 0, otherwise false.
Constraints
- •
1 <= nums.length <= 10^4 - •
0 <= nums[i] <= 10^5
Examples
Example 1
nums = [2,3,1,1,4]
trueExample 2
nums = [3,2,1,0,4]
falseLearning Objectives
- Recognise reachability problems where only the farthest reachable boundary matters.
- Maintain a greedy invariant instead of exploring all possible jumps.
- Explain why every index up to the current farthest boundary is safe to scan.
- Identify the failure point when the scan index moves beyond reach.
Intuition
Greedy Insight: track the farthest reachable index seen so far. If you are scanning an index i that is at most farthest, then there is at least one valid sequence of jumps that gets you to i. From there, i + nums[i] may extend the reachable frontier.
The tempting wrong idea is to choose the largest immediate jump at every position. That can skip useful launch points. The greedy state is not the chosen path; it is the best frontier produced by all launch points discovered so far. Once the frontier reaches the last index, the answer is already true. If the scan ever passes the frontier, no future index can help because future indices are unreachable.
Common mistakes
- ×Choosing the locally largest jump length instead of tracking the farthest reachable frontier.
- ×Continuing to update reach from an index that is already unreachable.
- ×Using an O(n) DP table when the greedy frontier is the only state needed.
- ×Forgetting that a one-element array is already at the last index.
Algorithm Explanation
Greedy strategy
Keep one variable, farthest, meaning the maximum index reachable using any scanned position. Scan from left to right. For each reachable index, extend farthest with i + nums[i].
Why it works
All indices from 0 through farthest are reachable by definition of the frontier. Therefore scanning them in order does not miss any valid launch point. An unreachable index cannot contribute to any real path, so the first index greater than farthest proves failure.
Proof of correctness
Maintain the invariant that before processing index i, farthest is the farthest index reachable using only launch points before i. If i > farthest, then no processed launch point reaches i, and no unprocessed launch point can be used because reaching it would require first crossing i. So returning false is correct. Otherwise i is reachable, and replacing any particular path choice with the best extension from reachable launch points cannot make the frontier worse. Updating farthest = max(farthest, i + nums[i]) preserves the invariant. If the invariant ever gives farthest >= n - 1, the last index is reachable, so returning true is correct.
Algorithm
- Set farthest = 0.
- For each index i from left to right, first check whether i > farthest.
- If so, return false because the scan has reached an unreachable gap.
- Otherwise update farthest with max(farthest, i + nums[i]).
- Return true once the end is reachable, or after the scan completes.
Solutions
Solution: Farthest reachable frontier
Track the farthest index reachable from all positions you have already proven reachable. The moment the scan index exceeds that frontier, a gap exists and the end cannot be reached.
Step-by-step
- Initialise farthest to 0 because you start at index 0.
- Iterate through the array from left to right.
- If the current index is greater than farthest, return false because no valid jump reaches it.
- Otherwise, extend farthest using index + nums[index].
- Return true immediately if farthest reaches the final index; otherwise the completed scan also means success.
O(n)
O(1)
Each index is scanned at most once and only the farthest frontier is stored.
Java implementation
Dry Run
Sample input
nums = [3,2,1,0,4]. Track the reachable frontier until the scan finds the gap before the last index.
| index | nums[index] | farthest before | reachable check | farthest after |
|---|---|---|---|---|
| 0 | 3 | 0 | 0 <= 0, reachable | 3 |
| 1 | 2 | 3 | 1 <= 3, reachable | 3 |
| 2 | 1 | 3 | 2 <= 3, reachable | 3 |
| 3 | 0 | 3 | 3 <= 3, reachable | 3 |
| 4 | 4 | 3 | 4 > 3, unreachable | not processed |
The scan reaches index 4 while farthest is still 3. Since index 4 is unreachable, the answer is false.
Interview Tips
Say the invariant out loud: every index up to farthest is reachable. That one sentence usually convinces the interviewer that you are not guessing. If asked for the actual path, keep parent choices separately; for the boolean question, the path is unnecessary noise.
Likely follow-ups
- How would you return one valid jump path instead of only a boolean?
- How would you find the minimum number of jumps once reachability is guaranteed?
- What changes if jumps can be negative and move left as well as right?
- Can you solve the same reachability question from the end moving backward?
Similar Problems
Key Takeaways
- Reachability can often be compressed to the farthest reachable boundary.
- Never update greedy state from an unreachable index.
- The first scan index beyond the frontier is a proof of failure.
- A path is not needed when the question only asks whether the end is reachable.