LeetCode: Jump Game II

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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

---

The idea is that we start looking from the start and each time we find the farthest position that we can reach until we get to the end point.

C++ Code:

/*
 * func: jump_ii
 * goal: find the minimum jump steps to the end of the array
 * @param A: the integer array A
 * @param n: the size of the array
 * return: the minimum steps
 */
/*
 * try to get as far as possilble each time
 * complexity: time O(n), space O(1)
 */
int jump_ii(int A[], int n){
    assert(n >= 0);
    for(int i=0; i<n; ++i){
        assert(A[i] >= 0);
    }
    
    int result = 0;
    //Current farthest position we can reach
    int current = 0;
    //Previous farthest position we can reach with result steps
    int previous = 0;
    for(int i=0; i<n; ++i){
        if(i > previous){
            previous = current;
            ++result;
        }
        current = std::max(current, i+A[i]);
        
    }
    return result;
}

Python Code:

# func: find the fewest steps to reach the end
# @param A: a list of integers
# @return: fewest steps
# complexity: time O(n), space O(1)
def jump_ii(A):
    current = 0
    previous = 0
    result = 0
    for index in xrange(len(A)):
        if index > previous:
            previous = current
            result += 1
        current = max(current, A[index] + index)

    return result

Reference Link:

[closed] Jump Game II - LeetCode http://discuss.leetcode.com/questions/223/jump-game-ii