Jump Game
Problem
Given an array of non-negative integers nums, return true if you can reach the last index starting from the first index, where each element represents the maximum jump length at that position.
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁵
Example
nums = [2,3,1,1,4]trueStarting at index 0 with jump length 2, you can jump to index 1 or 2. From index 1 with jump length 3, you can jump directly to the last index 4. The algorithm works backward from the last index, updating the 'goal' to the earliest index that can reach it. Initially, the goal is index 4. At index 3, jump length 1 allows reaching index 4, so the goal updates to 3. At index 1, jump length 3 allows reaching index 3, so the goal updates to 1. Finally, since the goal is 1 and index 0 can jump to index 1, the goal updates to 0, confirming the last index is reachable from the start.
Approach
Straightforward Solution
A brute-force approach tries all possible jumps from each index, exploring all paths recursively or via BFS/DFS. This leads to exponential or O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
The fundamental truth is that to reach the last index, there must exist a chain of indices where each index can jump to the next, eventually reaching the end. This can be reframed as a backward reachability problem: if an index can reach the 'goal', then that index becomes the new goal.
Path to Optimal
The key insight is to work backward from the last index, maintaining a 'goal' index that represents the earliest position from which the end is reachable. Iterating from right to left, if the current index can jump to or beyond the goal, update the goal to the current index. If after processing all indices the goal is 0, the last index is reachable from the start.
Optimal Approach
Use a single pass from the end of the array to the beginning. Initialize goal as the last index. For each index i from right to left, check if i + nums[i] >= goal. If yes, update goal to i. After the loop, return true if goal is 0, false otherwise. This approach runs in O(n) time and O(1) space.
Time
O(n)
The algorithm iterates through the array once from right to left, performing constant-time checks and updates per element.
Space
O(1)
Only a few variables are used to track the goal index and loop counters, with no additional data structures proportional to input size.
Pattern Spotlight
Greedy Algorithms (Backward Reachability)
When a problem asks if a target is reachable via jumps or steps, consider working backward from the target, greedily updating the earliest reachable position to efficiently collapse the search space.
Solution
| 1 | class Solution:
|
| 2 | def canJump(self, nums: list[int]) -> bool:
|
| 3 | goal = len(nums) - 1
|
| 4 |
|
| 5 | for i in range(len(nums) - 1, -1, -1):
|
| 6 | if i + nums[i] >= goal:
|
| 7 | goal = i
|
| 8 |
|
| 9 | return goal == 0 |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean canJump(int[] nums) { |
| 5 | int goal = nums.length - 1; |
| 6 | for (int i = nums.length - 1; i >= 0; i--) { |
| 7 | if (i + nums[i] >= goal) { |
| 8 | goal = i; |
| 9 | } |
| 10 | } |
| 11 | return goal == 0; |
| 12 | } |
| 13 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | bool canJump(vector<int>& nums) { |
| 8 | int goal = nums.size() - 1; |
| 9 | for (int i = (int)nums.size() - 1; i >= 0; i--) { |
| 10 | if (i + nums[i] >= goal) { |
| 11 | goal = i; |
| 12 | } |
| 13 | } |
| 14 | return goal == 0; |
| 15 | } |
| 16 | }; |
| 1 | var canJump = function(nums) { |
| 2 | let goal = nums.length - 1; |
| 3 | for (let i = nums.length - 1; i >= 0; i--) { |
| 4 | if (i + nums[i] >= goal) { |
| 5 | goal = i; |
| 6 | } |
| 7 | } |
| 8 | return goal === 0; |
| 9 | }; |
Step-by-Step Solution
Initialize Goal as Last Index to Represent Target Reachability
| 3 | goal = len(nums) - 1
|
Objective
To set the initial target position as the last index, which the algorithm will attempt to reach from earlier indices.
Key Insight
By defining the goal as the last index, the algorithm frames the problem as a backward search: each index tries to see if it can reach the current goal. This transforms the forward jump problem into a backward reachability problem, simplifying the logic and enabling a greedy solution.
Interview Quick-Check
Core Logic
Setting the goal as the last index establishes the target that all earlier indices attempt to reach.
State & Boundaries
The goal variable is updated only when an index can reach or surpass it, ensuring it always points to the earliest reachable position.
Iterate Backward to Update Goal Based on Reachability
| 5 | for i in range(len(nums) - 1, -1, -1):
|
| 6 | if i + nums[i] >= goal:
|
| 7 | goal = i
|
Objective
To scan the array from right to left, updating the goal whenever an index can jump to or beyond it.
Key Insight
By iterating backward, the algorithm checks if the current index can reach the goal. If it can, the goal moves left to this index, effectively shrinking the target window. This greedy contraction ensures that only indices capable of reaching the end remain as candidates, collapsing the problem into a simple linear scan.
Interview Quick-Check
Core Logic
The backward iteration combined with the goal update captures the essence of the greedy approach, progressively moving the goal leftward.
Common Pitfalls & Bugs
A common mistake is iterating forward or failing to update the goal correctly, which breaks the greedy logic and leads to incorrect results.
Complexity
This single backward pass ensures O(n) time complexity without extra space.
Return True if Start Index Can Reach the Goal
| 9 | return goal == 0 |
Objective
To determine if the first index can reach the last index by checking if the goal has moved to 0.
Key Insight
If after the backward iteration the goal is 0, it means the start index can reach the last index through a chain of reachable positions. Returning goal == 0 succinctly captures the final answer without extra computation.
Interview Quick-Check
Core Logic
Returning whether goal equals 0 directly answers if the start index can reach the end.
State & Boundaries
If goal is not 0, it means no sequence of jumps from the start can reach the last index.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if i + nums[i] >= goal:Check if the current index can reach or surpass the current goal.
This condition identifies indices that can jump directly to the goal, allowing the goal to move leftward and shrink the target window.
goal = iUpdate the goal to the current index if it can reach the previous goal.
Updating the goal to the current index contracts the problem space, representing the earliest reachable position from which the end can be reached, which is the core greedy step.
goal = len(nums) - 1Initialize the goal index as the last index of the array.
Setting the goal to the last index frames the problem as a backward reachability check, where the goal represents the earliest position from which the end can be reached.
return goal == 0Return true if the goal has moved to the start index, false otherwise.
If the goal is 0, it confirms the start index can reach the last index through a chain of reachable jumps; otherwise, it cannot.
for i in range(len(nums) - 1, -1, -1):Iterate backward through the array from the last index to the first.
Backward iteration is essential to update the goal progressively from the end towards the start, enabling a greedy contraction of the reachable target.
Test Your Understanding
Why does updating the goal index backward guarantee that if the goal reaches 0, the last index is reachable from the start?
Because the goal always represents the earliest index from which the end can be reached. If the start index can reach this goal, it means there exists a sequence of jumps from the start to the end, confirming reachability.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Jump Game from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Jump Game drill