Jump Game II
MedPrompt
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i]andi + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1000- It's guaranteed that you can reach
nums[n - 1].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a dp array where dp[i] stores the minimum number of jumps required to reach the last index from index i. We compute this array from the end to the beginning.
Algorithm
- Create an integer array
dpof sizenand initialize its values to a large number to represent infinity. - Set
dp[n-1] = 0. - Loop from
i = n-2down to0:- For each
i, loop fromj = i + 1tomin(n - 1, i + nums[i]). - Update
dp[i]withmin(dp[i], 1 + dp[j]).
- For each
- The final answer is
dp[0].
Walkthrough
This approach uses a bottom-up dynamic programming strategy. We define an array dp where dp[i] represents the minimum number of jumps needed to reach the last index n-1 from index i. Our ultimate goal is to find dp[0].
The logic is as follows:
- The base case is
dp[n-1] = 0, since we are already at the last index and require no jumps. - We then iterate backward from
i = n-2down to0. For each indexi, we consider all possible jumps we can make, which land us at an indexj(wherei < j <= i + nums[i]). - The minimum jumps from
iwould be 1 (for the current jump) plus the minimum jumps required from the landing positionj. - So, the recurrence relation is:
dp[i] = 1 + min(dp[j])for all reachablej. - We find this minimum by iterating through all possible
jfor a giveniand then updatedp[i].
import java.util.Arrays; class Solution { public int jump(int[] nums) { int n = nums.length; int[] dp = new int[n]; // Initialize dp array with a value representing infinity Arrays.fill(dp, Integer.MAX_VALUE); // Base case: 0 jumps needed from the last index to itself dp[n - 1] = 0; // Build the dp table from right to left for (int i = n - 2; i >= 0; i--) { int maxJump = i + nums[i]; for (int j = i + 1; j <= Math.min(n - 1, maxJump); j++) { // If index j is reachable from the end if (dp[j] != Integer.MAX_VALUE) { // Update dp[i] with the minimum jumps dp[i] = Math.min(dp[i], 1 + dp[j]); } } } return dp[0]; }}Complexity
Time
O(n^2)
Space
O(n)
Trade-offs
Pros
Conceptually simpler to understand than the greedy approach if you are familiar with DP.
Correctly solves the problem by exploring all possibilities in a structured way.
Cons
Not the most efficient solution. The time complexity can be high if the jump lengths are large, potentially leading to a 'Time Limit Exceeded' error on larger test cases.
This is the most optimal approach, which solves the problem in linear time. The core idea is to always make a jump that allows us to reach the farthest possible index. This can be visualized as a Breadth-First Search (BFS) where each jump constitutes moving to the next level of reachable indices.
Algorithm
- Initialize
jumps = 0,current_end = 0,farthest = 0. - Loop through the array from
i = 0ton-2:- Update
farthest = max(farthest, i + nums[i]). - If
i == current_end:- Increment
jumps. - Set
current_end = farthest.
- Increment
- Update
- Return
jumps.
Walkthrough
This is a highly efficient greedy approach that solves the problem in a single pass. The idea is to think of the jumps in terms of levels, similar to a Breadth-First Search (BFS). At each step, we want to make a jump that gives us the maximum possible reach for the next step.
We use three main variables:
jumps: Counts the total number of jumps made.current_end: The farthest index that can be reached with the current number ofjumps. This represents the boundary of the current 'level' in our BFS analogy.farthest: The farthest index that can be reached from any position within the current level.
The algorithm proceeds as follows:
- We iterate through the array from
i = 0ton-2. - In each iteration, we update
farthestby calculatingi + nums[i]and taking the maximum with the existingfarthest. This tells us the maximum reach we can achieve from the current level. - When our iterator
ireachescurrent_end, it means we have explored all indices reachable with the current number of jumps. We must now 'commit' to a jump. We incrementjumpsand updatecurrent_endto the newfarthestpoint we've discovered. This newcurrent_endbecomes the boundary for our next level of exploration. - This process guarantees that we are always making the jump that covers the most ground, thus minimizing the total number of jumps.
class Solution { public int jump(int[] nums) { int n = nums.length; if (n <= 1) { return 0; } int jumps = 0; // The end of the range that can be reached with the current number of jumps int current_end = 0; // The farthest index that can be reached from the current range int farthest = 0; // We iterate up to n-2 because we don't need to jump from the last element for (int i = 0; i < n - 1; i++) { // Update the farthest index we can reach farthest = Math.max(farthest, i + nums[i]); // If we have reached the end of the current jump's reach if (i == current_end) { // We must take another jump jumps++; // The new reach is the farthest we've found so far current_end = farthest; // Optimization: if the new end already covers the last index, we are done. if (current_end >= n - 1) { break; } } } return jumps; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal space usage (O(1)).
Cons
The logic can be less intuitive to grasp compared to the straightforward DP approach.
Solutions
Solution
public class Solution { public int Jump ( int [] nums ) { int ans = 0 , mx = 0 , last = 0 ; for ( int i = 0 ; i < nums . Length - 1 ; ++ i ) { mx = Math . Max ( mx , i + nums [ i ]); if ( last == i ) { ++ ans ; last = mx ; } } return ans ; } }class Solution {public int jump(int[] nums) { int ans = 0, mx = 0, last = 0; for (int i = 0; i < nums.length - 1; ++i) { mx = Math.max(mx, i + nums[i]); if (last == i) { ++ans; last = mx; } } return ans; }}class Solution {public: int jump(vector<int> &nums) { int ans = 0, mx = 0, last = 0; for (int i = 0; i < nums.size() - 1; ++i) { mx = max(mx, i + nums[i]); if (last == i) { ++ans; last = mx; } } return ans; }};class Solution : def jump ( self , nums : List [ int ]) -> int : current_reach = next_reach = steps = 0 # stop at 2nd-to-last, not the last index. # because, eg. nums=[1,0] or nums=[0,0], # just check the 2nd-to-last then we can decide if able to reach end # eg. - if input is [0], then 0 step needed for i , num in enumerate ( nums [: - 1 ]): next_reach = max ( next_reach , i + num ) if i == current_reach : current_reach = next_reach # update next-reach before if check steps += 1 # in question, guarenteed can reach end. or else need more check return steps ############ class Solution ( object ): def jump ( self , nums ): """ :type nums: List[int] :rtype: int """ pos = 0 ans = 0 bound = len ( nums ) while pos < len ( nums ) - 1 : dis = nums [ pos ] farthest = posToFarthest = 0 for i in range ( pos + 1 , min ( pos + dis + 1 , bound )): canReach = i + nums [ i ] if i == len ( nums ) - 1 : return ans + 1 if canReach > farthest : farthest = canReach posToFarthest = i ans += 1 pos = posToFarthest return ansVideo 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.