Jump Game

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.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Naive Way: I first think about Greedy. Go as far as possible each jump. But a future longer jump may lie in previous step. So I just think greedy is not able to handle this problem. Then I turn to DP. It seems DP will handle this problem easily.The basic logic is

opt[i] // whether a position can be reached or not
// base case
opt[0] = true;
// iteration
opt[i] = (opt[t] && A[t]+t >= i) for all 0<=t < i

But this approach get Time Limited Error.

An O(n^2) DP will get TLE, which implies an O(n) solution exists.

Then I think about DFS with path memorizing. Start from the end, trace backward to see if a particular position can reach the final stage. I am having trouble correctly writing the algorithm so far.


An ideal approach is a greedy one. Keep a range [start, end] that you are going to traversal. Update the range [end, new_end] according to farest distance one can go on [start, end].

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     if(A == null || A.length==0) return true;  
     int start = 0, end = A[0];  
     while(start <= end){  
       if(end >= A.length-1) return true;  
       int pre_end = end;  
       for(int i = start;i <= pre_end;i++)  
         end = Math.max(end, i+A[i]);  
       start = pre_end+1;  
     }  
     return false;  
   }  
 }  

Improved Way: A much more simple greedy idea. Update current coverage each step.

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     int coverage = 0;  
     for(int i = 0;i < A.length;i++)  
       if(coverage < i)   
         return false;  
       else  
         coverage = Math.max(coverage, A[i]+i);  
     return true;  
   }  
 }