C++ O(n) time, O(1) space complexity


  • 1
    J
        int jump(vector<int>& nums) {
    	if (nums.size() <= 1) return 0;
    
    	int count = 0, pos = 0, nextPos = 0, maxJump = nums[0];
    	while (pos + maxJump < nums.size() - 1) {
    		nextPos = pos + maxJump;
    		maxJump = 0;
    		while (pos < nextPos) {
    			maxJump = max(maxJump, nums[pos]);
    			pos++;
    			maxJump--;
    		}
    		maxJump = max(maxJump, nums[pos]);
    		count++;
    	}
    
    	return count + 1;
    }

Log in to reply
 

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