Share my 9ms C++ solution, O(n) space & time


  • 0
    R
    int jump(vector<int>& nums) {
            int i = 0, j = 1, n = nums.size(), num = 0;
            vector<int> steps(n, 0);
            while (i < n)
            {
                num = nums[i] - j + i + 1;
                while (j < n && num > 0)
                {
                    steps[j] = steps[i] + 1;
                    --num, ++j;
                }
                if (j == n) break;
                ++i;
            }
            return steps[n-1];
        }
    

Log in to reply
 

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