Jump Game II

MEDIUM

Description

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] and
i + 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 <= 10⁴
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Approaches

Checkout 2 different approaches to solve Jump Game II. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

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 dp of size n and initialize its values to a large number to represent infinity.
Set dp[n-1] = 0.
Loop from i = n-2 down to 0:
- For each i, loop from j = i + 1 to min(n - 1, i + nums[i]).
- Update dp[i] with min(dp[i], 1 + dp[j]).
The final answer is dp[0].

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-2 down to 0. For each index i, we consider all possible jumps we can make, which land us at an index j (where i < j <= i + nums[i]).
The minimum jumps from i would be 1 (for the current jump) plus the minimum jumps required from the landing position j.
So, the recurrence relation is: dp[i] = 1 + min(dp[j]) for all reachable j.
We find this minimum by iterating through all possible j for a given i and then update dp[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 Analysis

Time Complexity: O(n^2)Space Complexity: O(n)

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Jump Game II. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Jump Game II

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Adobe |Agoda |Amazon |Apple |