4 line C++ solution with 2 for-statement, O(n) time, O(1) space


  • 1
    S

    If you can reach position i, you can reach position i - 1 as well. So, that means the maximum jump length from position i should be the maximum of nums[i] and nums[i - 1] - 1

            for (int i = 1; i < nums.size(); ++i) nums[i] = max(nums[i - 1] - 1, nums[i]);
            int step = 0;
            for (int curr = 0; curr < nums.size() - 1; curr += nums[curr]) ++step;
            return step;
    

Log in to reply
 

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