Greedy, O(n) time complexity, O(1) space


  • 0
    J
    class Solution {
    public:
        int jump(vector<int>& nums) {
            if (nums.size() < 2) return 0;
            int max2current = nums[0];
            int i = 1; 
            int step = 0; 
            int start = nums[0];
            while (i < nums.size()) {
                max2current--;
                start--;
                if (nums[i] > max2current)
                    max2current = nums[i];
                if (start == 0) {
                    if (i != nums.size()-1)start = max2current;
                    step++;
                }
                i++;
            }
            if (start > 0) step++;
            return step;
        }
    };
    

Log in to reply
 

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