O(n) solution without DP


#1

int Solution::canJump(vector &A) {
if(A.size() == 1) return 1;
int arr[1000000];
for(int i=0;i<1000000;i++){
arr[i] = 1;
}
int maxi = -1;
int prev = -1;
for(int i=0;i<A.size()-1;i++){
int k = A[i];
if((i+k)>maxi){
maxi = i+k;
arr[maxi+1] = 0;
if(prev<=(i+k) && prev>i){
arr[prev] = 1;
}
prev = maxi +1;
}

}

for(int k=1;k<A.size();k++){
    
    if(arr[k] == 0) return 0;
}

return 1;

}