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.
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,
- When we reach index with element 0 we can’t jump further.
- We are assuming that we won’t have negative element in the array.
Program
[code lang=”java”]
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;
}
}
[/code]
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