#LeetCode: Java Solution of Jump Game problem

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Example 1:
Input: [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: [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.

GIT URL: Java Solution of Leet Code's Jump Game problem

Java Solution 1 :

Second Solution of Leet Code's Jump Game problem: Last Known Position

Algorithm:
1). We will maintain a variable lastAccuratePosition from which we can reach the last position. Since we can reach the last position from the last index we initialize lastAccuratePosition with the index of last element (i.e nums.length-1).
2). Now we will start iterating the input array from right (second last position) to the left.
3). In each iteration we will calculate furthestJump which is the summation of index and the value at that index (i.e nums[i]+i).
4). We will check if furthestJump is greater than or equal to lastAccuratePosition. If yes, then we will update the value of lastAccuratePosition with the current index.
5). After the iteration we will check if lastAccuratePosition is zero return true, else return false.

GIT URL: Java Solution of Leet Code's Jump Game problem

Java Solution 2 :

Third Solution of Leet Code's Jump Game problem: Dynamic Programming Top-down

1). We will start marking each index with a certain value (let's say GOOD, BAD and DONTNO), initially all the index's (except the last one) will be marked as DONTNO. We will start computing if the index is GOOD or BAD. Once the index is marked as GOOD or BAD, we won't change it. Since the value is not going to change, that's means it will be computed only once. We store these marked values let's create a array with a name valNums.
2). We will write a recursive function jumpAllowed(). First we will check if the index is not DONTNO (i.e either GOOD or BAD) and if yes, then return true or false. Otherwise we will call jumpAllowed() recursively.
3). The furthestJump from any position could be value at that position or the length of input array (which ever is less)
4). Once we determine the value of the current index, we store it in valNums.

GIT URL: Java Solution of Leet Code's Jump Game problem using Dynamic Programming Top-down

Java Solution 3 :

Fourth Solution of Leet Code's Jump Game problem: Dynamic Programming Bottom-up
We will change our top-down approach to bottom-up, while doing this we will eliminate the recursion. Since we are not using recursive function jumpAllowed(), we no longer have the method stack overhead.

In this approach also, we will start marking each index with a certain value (let's say GOOD, BAD and DONTNO), initially all the index's (except the last one) will be marked as DONTNO. We will start computing if the index is GOOD or BAD. Once the index is marked as GOOD or BAD, we won't change it.


We start from the right of the array, every time we will query a position to our right. If that position has already be determined as being GOOD or BAD, we won't recurse it anymore, as we will always get the value from valNums.

GIT URL: Java Solution of Leet Code's Jump Game problem using Dynamic Programming Bottom-Up

Java Solution 4 :

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa..