LeetCode: 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.

---

I solved this problem in two ways. One is recursive, the subproblem is that if the node next to the last node can be accessed plus its distance to the last element. The other one is iterative, which I got from online. Its idea is to record the farthest index we can reach by current index.

C++ Code:

/*
 * func: can_jump
 * goal: to determine if it is possible to reach the last index
 * @param A: input array A
 * @param n: the size of the array
 * return: true or false
 */
bool can_jump(int A[], int n){
    if(n <= 1){
        return true;
    }
    //Start index is the index next to the last one, which will be the input for
    //the recursive call next time
    int start_index = n-2;
    //If based on the current start index, we cannot get to the last one,
    //Such as [2, 0, 4], we need to go leftside by one step until to reach
    //an available element.
    while(start_index >=0 && A[start_index] < n - 1 - start_index){
        --start_index;
    }
    //If we already get to the starting position of the array, it means that
    //we cannot get to the end
    if(start_index < 0){
        return false;
    }else{
        return can_jump(A, start_index + 1);
    }
}

Python Code:

# func: check if the we can reach the last element of the list
# @param A: input list
# complexity: time O(n), space O(1)
def can_jump(A):
    #Most farthest position we can reach until now
    reachable = 1
    i = 0
    while i < reachable < len(A):
        reachable = max(reachable, A[i] + i + 1)

    return reachable >= len(A)

1. [closed] Jump Game - LeetCode: http://discuss.leetcode.com/questions/232/jump-game