Skip to main content

Jump Game

Level - Medium

Statement​

given an array of non-negative integers nums, you are initially positioned at the first index of the array, at each index nums[i] represents the maximum jump length you can take from the current index i. You have to return minimum number of jumps needed to reach at the end nums[n - 1].

Example 1​

Input: nums = [2,3,0,1,4]

Output: 2

Explaination : in above nums this jump route 0th index -> 1th index -> 4th index will give you minimum jumps to reach at the end. so in total there are 2 jumps needed.

Constraints​

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

Brute Force Approach​

  • first the approach which came in our mind is to try out all possible ways in which we can reach from index=0 to index=n-1.
  • this can only be possible with the help of recursion.
  • there can be multiple ways to reach from index=0 to index=n-1.
  • we have to select the way in which we need minimum jumps.

Recursive Tree​

Recursion Dry Run​

class Solution {
    // given in constraints
    int MAX_JUMPS_COUNT = 10000;
    public int dfs(int[] nums,int index){
        // index beyond n-1 is not acceptable so return MAX_JUMP_COUNT
        if(index>=nums.length){
            return MAX_JUMPS_COUNT;
        }
        // we have reached to last index
        if(index==nums.length-1){
            return 0;
        }

        int min_jump = MAX_JUMPS_COUNT;
        for(int i=1;i<=nums[index];i++){
            int jump_count = 1+dfs(nums,index+i);
            min_jump = Math.min(min_jump,jump_count);
        }
        return min_jump;
    }

    public int jump(int[] nums) {
        return dfs(nums,0);
    }
}

Complexity​

Time Complexity:

O(N^N)

Space Complexity:

O(N)

Optimize this Approach by Memoization​

Memoization is the technique to save the previous results

Explaination​

class Solution {
    // given in constraints
    int MAX_JUMPS_COUNT = 10000;
    public int dfs(int[] nums,int index,int[] memo){
        if(index>=nums.length){
            return MAX_JUMPS_COUNT;
        }
        if(index==nums.length-1){
            return 0;
        }
        if(memo[index]!=-1)return memo[index];
        int min_jump = MAX_JUMPS_COUNT;
        for(int i=1;i<=nums[index];i++){
            int jump_count = 1+dfs(nums,index+i,memo);
            min_jump = Math.min(min_jump,jump_count);
        }
        memo[index] = min_jump;
        return min_jump;
    }
    public int jump(int[] nums) {
        int[] memo = new int[nums.length];
        Arrays.fill(memo,-1);
        return dfs(nums,0,memo);
    }
}

Complexity​

Time Complexity:

O(N*N)

Space Complexity:

O(N)

note

in an interview you don't need to tell Iterative approach but if you want to grasp DP Concepts Iterative Method will help you to better understand the question

Iterative Approach/Bottom Up Approach​

Explaination​

  • iterative / bottom up approach , create a 1D DP array dp[]
  • dp[i] represents the min jump need from i to n-1 index
  • dp[n-1] = 0 as it is the last index
  • start from n-2 index and at each index:
    • try all jumps from gap = 1 to gap = nums[ index ]
    • dp[index] = min jump from index to n-index
class Solution {
    // given in constraints
    int MAX_JUMPS_COUNT = 10000;
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i=n-2;i>=0;i--){
            int min_jump = MAX_JUMPS_COUNT;
            for(int gap=1;gap<=nums[i];gap++){
                if(gap+i < nums.length)
                min_jump = Math.min(min_jump,1+dp[i+gap]);
            }
            dp[i] = min_jump;
        }
        return dp[0];
    }
}

Complexity​

Time Complexity:

O(N*N)

Space Complexity:

O(N)

note

N denotes nums array length