Data Structures & Algorithms in Java – Dynamic Programming – Jump Game

Problem:

Given an array of numbers which indicate how many positions maximum you can jump from that index position , find out if you can reach the end of the array from the beginning.

For example:

For the input [2,3,1,1,4]

You can jump maximum 2 positions from index 0, 3 positions from index 1 , 1 position from index 2 and so on.

From index 0 you can make it to the last index by jumping 1 position from index 0 , which lands you in index 1 from where you can make 3 jumps to make it to the last index.

So you return true.

For the input [3,2,1,0,4]

The maximum jumps you can make from index 0 is 3 which lands you in index 3 where the maximum jumps you can make is 0.

So you cant proceed further.

Similarly even if you make a jump to index 1 from index 0 (from index 0 you can make utmost 3 jumps and at least 1 jump) you can make maximum 2 jumps which also lands you in index 3 from where you cannot proceed further.

So return false.

Try out the solution here:

https://leetcode.com/problems/jump-game/

Solution:

Hint:

• At every index position calculate the maximum index you can jump to.

ALGORITHM:

STEP1: If there is only one element in the input , then return true , since anyway you start from the begining

STEP2: Initialize a variable to represent the maximum index reachable to 0.

STEP3: For every index position , calculate the maximum of the previous maximum index that can be reached and the maximum index position that can be reached from the current index.

STEP 3b: At any point in the above iteration , If the current index is greater than the maximum value , then you cannot jump further so return false

STEP 3c: At any point in the iteration , if the maximum index that can be reached exceeds or equals the last index position then return true.

STEP4: Return false by default.

Code:

class Solution {
    public boolean canJump(int[] nums) {
        
        if(nums.length == 1){
            
            return true;
        }

        
        int max = 0;
        
        for(int i=0;i<nums.length;i++){
            
            
            if(i>max){
                
                return false;
            }
            

            max = Math.max(max,i+nums[i]);
                
                
                if(max >= nums.length-1){
                    
                    return true;
                }
         
            }
            
  
        return false;
        
    }
}

The time complexity of the above algorithm is O(n) and space complexity is O(1)

Alternate solution:

An alternate solution exists of O(n) too .

In this case , you start from the last index.

Then you check the previous index value.

If you can reach the last index from the previous index then you update the last index to the previous index and continue this until you reach the first index.

This is because once you can reach an index position from another position , then all you need to bother about is whether you can reach that another position.

So you keep updating the last index.

If the last index becomes 0 then it means you have reached the beginning so you return true.

Code:

class Solution {
  public boolean canJump(int nums[]) {
      

      
      int last = nums.length - 1;
    
      for(int i = nums.length - 2 ;i>=0;i--){
          
          
          if(nums[i] + i >= last){
              
              last = i;
          }
      }
    
    return last ==0;
}
}

Even though this solution looks more elegant than the first one , you always need to iterate through the entire array to find out the solution whereas in the previous case in the best cases you can return true or false even before the loop completes.

That’s it!