# Java 98% Percentile Solution

• The easiest way to think about this problem is to ask are the elements with a 0 value avoidable? this is the algorithm that I constructed to answer this question.Starting from the second to last element in the array we continue to decrement towards the start of the array. Only stopping if we hit an element with a value of 0; in this case we evaluate if there exist an element somewhere at the start of the array which has a jump value large enough to jump over this 0 value element.

``````public class Solution {
public boolean canJump(int[] nums) {
if(nums.length < 2) return true;

for(int curr = nums.length-2; curr>=0;curr--){
if(nums[curr] == 0){
int neededJumps = 1;
while(neededJumps > nums[curr]){
neededJumps++;
curr--;
if(curr < 0) return false;
}
}
}
return true;
}
}``````

• This is really awesome!

• That if condition is not needed I guess..

• Here is my code, trying to be more concise

``````bool Solution::canJump_gap(vector<int>& nums) {
// when cannot jump from i to i + 1, must find k < i that can jump to i + 1

if (nums.size() <= 1)
return true;

int need_jumps = 1;
for (int i = nums.size() - 2; i > 0; --i) {
if (nums[i] < need_jumps) {
++need_jumps;
} else {
need_jumps = 1;
}
}
if (nums[0] < need_jumps) {
return false;
} else {
return true;
}

}
``````

I think it is similar to this solution, where it keeps the numbers of steps left, when going forward.
However, here we keep the numbers of steps needed, when going backward.

• @xsh6528
public boolean canJump(int[] nums) {
int last=nums.length-1;
int res=0;
for(int i=0;i<last&&res>=i;i++ ){
int tmp=i+nums[i];
if(tmp>res) res=tmp;
if(res>last) return true;
}
if(res<last) return false;
return true;
}

• @mlblount45
agree! here is my solution, but ...only 92.73%....sad

int len = nums.length;
if(len==1) {
return true;
}

``````for(int i = 0; i<len; i++) {
if(nums[i]== 0) {
if(i==0) return false;
if(i==len-1) return true;
for(int j = i-1;; j--) {
if(nums[j]>(i-j)) break;
if(j==0) return false;
}
}
}
``````

return true;

• Great idea
wrote a python version

``````class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
cur = len(nums)-1
needed = 0
while cur>0:
cur-=1
if nums[cur]<=needed: needed+=1
else:needed=0
return not needed
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.