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 use greed algorithm to jump to the next farthest element in the array with max(A[i]+i). Why do we need to also include the index? because if index is large means you are more close to the end. Some edge cases:

1. Do not jump to an element with array[i]==0
2. If you can jump to the end of the array, return true
3. After checking, if no available jump found (all 0s), return false.

public int jump(int[] A) {
        if (A==null||A.length==0) {
            return 0;
        }

        int steps = 0;
        int index = 0;        
        while(index<A.length-1) {          
            int maxJump = 0;
            int canJump = A[index]+index;
            int nextJumpIndex = 0;
            //scan from index+1 to A[index]+index or the last element in the array
            for (int i=index+1; i<=Math.min(canJump, A.length-1); i++) {
                //if we reach the last element, quit the loop
                if (i==A.length-1) {
                    return steps+1;
                }

                //skip 0 and if we can reach more, update the index
                if (A[i]!=0&&maxJump<A[i]+i) {
                    maxJump = A[i]+i;
                    nextJumpIndex = i;
                }
            }

            if (index<nextJumpIndex) {
                index = nextJumpIndex;
                steps++;
            } else {
                return -1;
            }
        }

        return steps;
    }