Jump Game
MedPrompt
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.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach is a straightforward brute-force method. We simulate all possible jump combinations recursively. Starting from the first index, we explore every possible jump. If any of these paths lead to the last index, we return true.
Algorithm
- Define a recursive function
canJumpFromPosition(position, nums). - If
positionis the last index, returntrue. - Calculate the furthest reachable index from
position:furthestJump = position + nums[position]. - Iterate from
position + 1tofurthestJump. - For each
nextPosition, recursively callcanJumpFromPosition(nextPosition, nums). - If the recursive call returns
true, returntrue. - If the loop finishes without finding a path, return
false. - The initial call is
canJumpFromPosition(0, nums).
Walkthrough
The core idea is a recursive function, say canJumpFrom(position, nums), which checks if the end can be reached from a given position.
-
Base Case: If
positionis the last index (nums.length - 1), we've successfully reached the end, so we returntrue. -
Recursive Step: From the current
position, we can jump to any index fromposition + 1up toposition + nums[position]. We iterate through all these possible next positions. For eachnextPosition, we make a recursive callcanJumpFrom(nextPosition, nums). If any of these recursive calls returntrue, it means we've found a valid path, and we can returntrueimmediately. -
Failure: If we try all possible jumps from the current
positionand none of them lead to a solution (i.e., all recursive calls returnfalse), it means the end is not reachable from thisposition. We then returnfalse.
This method explores all possible jump paths from the starting position, which can lead to a large number of redundant calculations.
class Solution { public boolean canJump(int[] nums) { return canJumpFromPosition(0, nums); } private boolean canJumpFromPosition(int position, int[] nums) { if (position >= nums.length - 1) { return true; } int furthestJump = nums[position]; // Iterate backwards from the furthest jump for a slight optimization // as longer jumps are more likely to reach the end faster. for (int jump = furthestJump; jump >= 1; jump--) { if (canJumpFromPosition(position + jump, nums)) { return true; } } return false; }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
This approach improves upon backtracking by using dynamic programming to avoid re-computing results for the same subproblems. We use an array, let's call it dp, to store whether the last index is reachable from each index i. We solve the problem iteratively, starting from the end of the array and working our way backward.
Algorithm
- Create a boolean array
dpof sizen, wherenis the length ofnums. - Set
dp[n-1] = true. - Iterate
ifromn-2down to0. - For each
i, find the furthest possible jump:furthestJump = i + nums[i]. - Iterate
jfromi+1tomin(furthestJump, n-1). - If
dp[j]istrue, it means we can reach the end fromi. Setdp[i] = trueand break the inner loop. - After the loops complete, return
dp[0].
Walkthrough
We create a boolean array dp of the same size as nums. dp[i] will be true if the last index is reachable from index i, and false otherwise.
-
Initialization: We know that the last index is reachable from itself, so we initialize
dp[n-1] = true. All otherdpentries are implicitlyfalse. -
Iteration: We iterate backward from the second-to-last index (
n-2) down to the start (0). For each indexi, we want to determinedp[i]. An indexiis 'good' if it can jump to another 'good' indexj. -
Logic: For each index
i, we check all the indicesjit can jump to (i.e.,i < j <= i + nums[i]). If we find any indexjfor whichdp[j]is alreadytrue, it means we can reach the end fromi(by jumping tojfirst). We then setdp[i] = trueand can stop checking for thisi. -
Result: After the loop finishes, the value of
dp[0]tells us whether the last index is reachable from the starting position.
class Solution { public 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--) { int furthestJump = Math.min(i + nums[i], n - 1); for (int j = i + 1; j <= furthestJump; j++) { if (dp[j]) { dp[i] = true; break; } } } return dp[0]; }}Complexity
Time
O(n^2)
Space
O(n)
Trade-offs
Pros
Guarantees a solution without timeouts for larger inputs compared to backtracking.
Systematic way to solve the problem by breaking it down into subproblems.
Cons
Time complexity of O(n^2) is not optimal.
Requires O(n) extra space for the DP table.
The most efficient solution uses a greedy strategy. Instead of determining if we can reach the end from the start, we can rephrase the problem: what is the leftmost index from which we can reach the end? We can solve this by iterating backward from the end of the array.
Algorithm
- Initialize a variable
lastGoodPositiontonums.length - 1. - Iterate
ifromnums.length - 2down to0. - Check if the current position
ican reachlastGoodPosition(i.e.,i + nums[i] >= lastGoodPosition). - If it can, update
lastGoodPositiontoi. - After the loop, if
lastGoodPositionis0, returntrue. Otherwise, returnfalse.
Walkthrough
The key insight is to track the leftmost 'good' index. A 'good' index is one from which we can reach the last index.
-
Initialization: We start by marking the last index (
n-1) as our initial leftmost 'good' position, let's call thislastGoodPosition. -
Iteration: We then iterate backward through the array, from index
n-2down to0. -
Greedy Choice: At each index
i, we check if we can reach the currentlastGoodPositionfromi. The condition for this isi + nums[i] >= lastGoodPosition. If we can, it means that indexiis now a new, even more-left 'good' position. So, we greedily updatelastGoodPosition = i. -
Result: We continue this process until we've checked all indices down to
0. If our finallastGoodPositionis0, it means the starting index is a 'good' position, and thus we can reach the end. Otherwise, it's impossible.
class Solution { public boolean canJump(int[] nums) { int lastGoodPosition = nums.length - 1; for (int i = nums.length - 2; i >= 0; i--) { if (i + nums[i] >= lastGoodPosition) { lastGoodPosition = i; } } return lastGoodPosition == 0; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Simple and elegant implementation.
Cons
The greedy logic might be less obvious to discover compared to DP or backtracking.
Solutions
Solution
public class Solution { public bool CanJump(int[] nums) { int mx = 0; for (int i = 0; i < nums.Length; ++i) { if (mx < i) { return false; } mx = Math.Max(mx, i + nums[i]); } return true; }}class Solution {public boolean canJump(int[] nums) { int mx = 0; for (int i = 0; i < nums.length; ++i) { if (mx < i) { return false; } mx = Math.max(mx, i + nums[i]); } return true; }}/** * @param {number[]} nums * @return {boolean} */ var canJump = function ( nums,) { let mx = 0; for (let i = 0; i < nums.length; ++i) { if (mx < i) { return false; } mx = Math.max(mx, i + nums[i]); } return true;};class Solution {public: bool canJump(vector<int> &nums) { int mx = 0; for (int i = 0; i < nums.size(); ++i) { if (mx < i) { return false; } mx = max(mx, i + nums[i]); } return true; }};class Solution : def canJump ( self , nums : List [ int ]) -> bool : mx = 0 for i , x in enumerate ( nums ): if mx < i : return False mx = max ( mx , i + x ) return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.