Jump Game Interview Question

Jump Game Interview Question

We have to play jump game. You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Jump Game Approach:

You are starting from the first index. Based on the value present in that index we can jump. For example, if we have 3 in in arr[0] then we have jump 1 or 2 or 3 steps from first index. We have 3 possibilities here.  As per the

After visiting 2 from 3, we have two possible jumps from that index.

Jump game

 

Value at an index = No of possibility of jumps from that index

We can image it like a tree ,

Our goal is to reach the last index. We have to find if any of the paths in tree lead us to the destination. Since it is like tree we can use recursion to traverse all the paths.

Let us take example [3,2,1,0,4]. Since we are using recursion, From the below diagram you can see that we visit Node 1 twice.

We know that we can’t reach last index from Node 1 after first visit itself. So to avoid repeated visits to invalid node we maintain a visited array. After visiting a Node we mark it as visited. Base cases are,

  1. When we reach index with element 0 we can’t jump further.
  2. We are assuming that we won’t have negative element in the array.

Program

class Solution {
    public boolean canJump(int[] nums) {
        
        boolean[] visited = new boolean[nums.length];
       return jump(0,nums,visited);
        
    }
    boolean jump(int index,int[] nums,boolean[] visited)
    {
        //Return true if we can reach the last position.  
        if(index >= nums.length-1)
            return true;
        
        //Already visited this index means. last position is not reachable from this position
       if(visited[index] == true)
       {
         return false;  
       } 
        
        //mark as visited
        visited[index] = true;    
        
        int currValue = nums[index];
        boolean ret = false;
        
        //Check all the possible jump from current value (Ex: value=3, jump=3,2,1)
        for(int val = currValue; val>0; val--)
        {
            
            ret = jump(index+val,nums,visited);
            //return will be overrided in next iteration so return once it is true
            if(ret == true)
            {
                return ret;
            }
        }
        return ret;
    }
}

Complexity

Time Complexity – We are visiting each node/element only once. Since we have n elements time complexity is O(n)

Space Complexity – O(n) since we use visited array of input array size

You Might Also like

C program to find Height of Binary Tree | Amazon

House Robber Interview Question

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x