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.

For example: Given array A =[2,3,1,1,4]

The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index.)

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

Approach 1: Brute Force

Like with standard brute force procedures, we build a tree carries all possibilities, and recur on those. Consider the example above when A =[2,3,1,1,4]. Beginning at index 0, we can jump 2 places [1,3], from 1, we can jump to [1], and from 3, [4,1,1]. Because we all explore all possible jump paths, the first time a BFS procedure identifies that a jump took it to the end of the array, the function immediately returns; as this is the shortest path. Both time and space complexity are exponential.

int jump_bf(vector<int>& nums) {
    if (nums.size() <= 1) return 0;

    int end = nums.size() - 1;
    queue<pair<int, int>> q;
    q.push({0,1}); // start index 0

    while (!q.empty()) {
        pair<int,int> index_lvl = q.front(); q.pop();
        int jump = nums[index_lvl.first];

        // check all indices after i, decrementing
        for (int i = min(jump, end); i > 0; i--) {
            if (i + index_lvl.first != end) {
                q.push({ i + index_lvl.first, index_lvl.second + 1 });
            }
            else return index_lvl.second;
        }
    }

    return 0;
}

Approach 2: Greedy BFS

The solution to a linear time complexity deals with knowing which path to take in the brute force procedure discussed earlier. Let's think about it. Beginning at index 0, we have [0:nums[0]] options to chose from. Which option ensures to be the most optimal? Well, if we take the maximum element, we know we can reach further out in the array. Potentially, it could exceed the size of the array, but that does not matter, because we can simply chose the end. This however, is not optimal. Consider the counter example of a decreasing vector. The algorithm would always select the next element, and only ever move 1 step closer to the end of the array. However, if we consider the index in addition to the element, we ensure that we optimally close to the end of the array. This is because moving an additional index forward is the same as if the previous element took you that same distance. Both the element and the index carry distance in the sense of begin being able to either jump further, or physically get further.

int jump(vector<int>& nums) {
    if (nums.size() <= 1) return 0;

    int start = 0;
    int end = nums.size();
    int jumps = 0;

    while (start < end - 1) {
        int max_jump = nums[start];
        int it_start = start + 1;
        int it_end = min(it_start + max_jump, end);
        if (it_end >= end)
            return jumps + 1;

        int max_val_and_index = INT_MIN;
        for (int i = it_start; i < it_end; i++) {
            if (nums[i] + i >= max_val_and_index) {
                max_val_and_index = nums[i] + i;
                start = i;
            }
        }
        jumps++;
    }

    return jumps;
}

Some Testing

int main()
{
    // this example demonstrates why always taking the
    // last avaiable maximum does not always work
    vector<int> nums10 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0 };
    assert(jump(nums10) == 2);

    vector<int> nums9 = { 1, 2, 1, 1, 1 };
    assert(jump(nums9) == 3);

    vector<int> nums7 = { 1,2,3 };
    assert(jump(nums7) == 2);

    vector<int> nums8 = { 2, 0, 2, 0, 1 };
    assert(jump(nums8) == 2);

    vector<int> nums6 = { 1, 2, 1, 8, 7, 2, 5 };
    assert(jump(nums6) == 3);

    vector<int> nums5 = {8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5 };
    assert(jump(nums5) == 13);

    vector<int> nums1 = { 2, 3, 1, 1, 4 };
    assert(jump(nums1) == 2);

    vector<int> nums2 = { 0 };
    assert(jump(nums2) == 0);

    vector<int> nums3 = { 1 };
    assert(jump(nums3) == 0);

    vector<int> nums4 = { 1, 2 };
    assert(jump(nums4) == 1);
}