O(n) solution


  • 0
    A

    I have two variables: curMax - current maximum index, where we can jump. newMax - till curMax we are finding new max index, where we can jump. When we reach curMax, we update it to newMax, increase number of step and will find new max.

    int jump(vector<int>& nums) {
        int curMax = 0, newMax = -1, step = 0;
        for (int i = 0; i < nums.size() - 1; ++i) {
            newMax = max(newMax, nums[i] + i);
            if (i == curMax) {
                curMax = newMax;
                newMax = -1;
                ++step;
            }
        }
        return step;
    }
    

  • 2

    Nice solution. Think you don't need to set newMax = -1; inside the if statement.


  • 0
    A

    @shenjunsu agree


Log in to reply
 

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