Jump Game II

<-M 45> Jump Game II

// Method 1
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int step = 0;
        int left = 0;
        int right = 0;
        
        if(n == 1)
            return 0;
        
        while(left <= right) {
            step++;
            const int old_right = right;
            for(int i = left; i <= old_right; i++) {
                int new_right = i + nums[i];
                if(new_right >= n - 1)
                    return step;
                
                if(new_right > right)
                    right = new_right;
            }
            left = old_right + 1;
        }
        return 0;
    }
};

// Method 2
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1 )
            return 0;       
        int maxi = 0;
        int curr = 0;
        int ans = 0;
        
        for(int i = 0; i < n - 1; i++) {
            maxi = max(maxi, nums[i] + i);
            if(maxi == n - 1) {
                return ans + 1;
            }
            if(i == curr) {
                curr = maxi;
                ans++;
            }
        }
        return ans;
    }
};