45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note: You can assume that you can always reach the last index.

Solution

Approach 1: (Time Limit Exceeded) DP -- O(N^2).

Approach 2: (Time Limit Exceeded) greedy -- O(N^2). Start from the target and find the first (from beginning) node that can reach the target. Then set that node as the new target and repeat the same process until we reach the first node.

Approach 3: greedy -- O(N). Keep 2 pointers: the current max reach (farthest index), and the max reach for the next hop. Go through the array, and keep expanding the next reach pointer.

Code (Python)

Approach 1:

    def jump(self, nums: List[int]) -> int:
        # DP -- O(N^2) -- TLE
        min_jumps = [0] + [float('inf') for _ in range(1, len(nums))]
        for i in range(len(nums)):
            for j in range(i + 1, min(len(nums), i + 1 + nums[i])):
                min_jumps[j] = min(min_jumps[j], min_jumps[i] + 1)
        return int(min_jumps[-1])
    

Approach 3:

    def jump(self, nums):
        # greedy -- O(1)
        # [[   max_reach    ]    next_reach    ]
        steps = 0
        max_reach = 0
        next_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                max_reach = next_reach
                steps += 1
            next_reach = max(next_reach, i + nums[i])
        return steps

Code (C++)

Approach 1:

// DP.
// Time Limit Exceeded.
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> minJump(n, n+1);
        minJump[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 1; j <= nums[i]; ++j)
            {
                if (i + j >= n)
                    break;
                minJump[i+j] = std::min(minJump[i+j],
                    minJump[i] + 1);
            }
        }
        return minJump[n-1];
    }
};

Approach 2:

// Greedy.
// Time Limit Exceeded.
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int target = n - 1;
        int count = 0;
        while (target > 0)
        {
            int i = 0;
            for (; i < target; ++i)
            {
                if (i + nums[i] >= target)
                    break;
            }
            if (i == target)
                return -1;
            target = i;
            count++;
        }
        return count;
    }
};

Approach 3:

// Greedy.
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int head = 0;
        int tail = 0;
        int count = 0;
        while (tail < n - 1)
        {
            int maxNext = tail;
            for (int i = head; i <= tail; ++i)
            {
                maxNext = std::max(maxNext, i + nums[i]);
            }
            head = tail + 1;
            tail = maxNext;
            count++;
        }
        return count;
    }
};