Solution to LeetCode Problems: Jump Game

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.


Thoughts:
Mark the last element as "reachable" since it is able to reach itself. Then traverse the array A[] backwards, and check if there is an element within the range the current element could reach marked as "reachable". If so, mark the current element as "reachable". The problem is solved when the first element is inspected.

Solution:

1. class Solution {  
2. public:  
3.     bool canJump(int A[], int n) {  
4.         // store the maximum index can be reached from the i-th index  
5.         vector<bool> reachable(n);  
6.         reachable[n-1] = true;  // it can always reach itself  
7.           
8.         auto reach_forward=[&reachable,n](const int index, const int dist) -> bool {  
9.             for(int fwd = index+1; fwd <= min(dist, n-1); ++fwd)  
10.                 if (reachable[fwd])   
11.                     return true;  
12.             return false;  
13.         };  
14.           
15.         // reverse iterate every previous element   
16.         for(int ri = n-2; ri>=0; --ri)  
17.             reachable[ri]=reach_forward(ri, A[ri]);  
18.               
19.         return reachable[0];  
20.     }  
21. };  

Thoughts:
The previous solution has the time complexity O(n^2). It works but too slow.

If we traverse the array forwardly, and mark the index of farthest element the current partition of the array as "so_far", then we can confirm the last element is reachable when "so_far" is larger than n-1 (we assume the first element has the index 0, as C/C++ defines). If we reached "so_far" but unable to update "so_far" to a value larger than n-1, then the last element cannot be reached. The array is iterated only once so the time complexity is O(n). So far so good.

Solution:

1. class Solution {  
2. public:  
3.     bool canJump(int A[], int n) {  
4.         // store the farthest element can be reached  
5.         int so_far = 0;  
6.           
7.         for(int iter=0; iter<=so_far; ++iter)  
8.             if ( (so_far = max(so_far, A[iter] + iter)) >= n-1 )  
9.                 return true;  
10.         return false;  
11.     }  
12. };