45 Jump Game II

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return 0;
        int i1 = 0, i2 = 0;
        int ijump = 0;
        while (true) {
            ijump += 1;
            int furthest = -1;
            for ( int i = i1;  i <= i2; i++ ) {
                furthest = max(furthest, i+nums[i]);
                if ( furthest >= n-1 ) return ijump;
            }
            i1 = i2+1;
            i2 = furthest;
        }
    }
};

Notes

• Starting from 0, and its furthest jump is i2 = nums[0].
• Scan from i1 = 1 to i2 = nums[0], find the next furthest position furthest. Then scan from i1 = i2+1 to i2 = furthest. Until furthest >= n-1.
• Note that once the new furthest is smaller than the previous furthest i2. One can never reach the end of the array.

Solution for Jump Game I

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return true;
        int furthest = 0, i = 0;
        while ( i <= furthest ) {
            furthest = max(furthest, nums[i] + i);
            if ( furthest >= n-1 ) return true;
            i += 1;
        }
        return false;
    }
};