Easy understand O(n) time, O(1) space code


  • 8
    N

    The main idea is using 2 integer to record the longest distance of current jump can arrive.
    If n jump cannot arrive at index i, it must jump one more time. Which means, the least jump time to get index i is (n+1).

     int jump(vector<int>& nums) {
        if (n <= 1)
            return 0;
        int i, n = nums.size(), lc, ln, step = 1;
        // lc means the longest distance can achieve by current jump
        // ln means the longest distance can achieve by next jump
    
        lc = nums[0], ln = nums[0]; //Initialize to index 0, the start point.
        for (i = 1; i < n; ++i)
        {
            if (i > lc) //current jump cannot get index i -->>> must jump one more time.
            {
                lc = ln;
                step++;
            }
            if (i + nums[i] > ln) //maintain the furthest distance of next jump can get
                ln = i + nums[i];
            if (lc >= n - 1) //current jump can achieve the last index
                return step;
        }
    }

Log in to reply
 

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