C++ O(n) Solution and detailed explanation


  • 0
    E
    class Solution {
    public:
        int jump(vector<int>& nums) {
            if(nums.size() <= 1) return 0;
            int left = 0, right = 0, count = 0, index = 0;
            while(true){
                right = index+nums[index];  // rightmost position jumping from current position
                if(right <= left) return -1;    // unable to reach the end
                if(right >= nums.size()-1) break; // can reach the end
                int max = INT_MIN;
                for( int k = left+1; k <= right; k++ ){ // find the one that can jump the farthest
                    if(k+nums[k] > max){
                        max = k+nums[k];
                        index = k;
                    }
                }
                left = right;
                count++;
            }
            return count+1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.