Scale Engineer

Jump Game II

Med
#0045Time: O(n^2)Space: O(n)30 companies
Patterns
Dynamic ProgrammingGreedy
Data structures
Array
Companies
AdobeAgodaAmazonApple

Prompt

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 <= 104
  • 0 <= 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 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].

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

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.

Solutions

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 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.

← Previous

Previous problem

Next →

Next problem