Alkesh

LeetCode - Jump Game II

Problem statement

Given an array of non-negative integers nums, 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.

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

Problem statement taken from: https://leetcode.com/problems/jump-game-ii/

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [2, 3, 0, 1, 4]
Output: 2

Constraints:

- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000

Explanation

The problem is an extension of our old blog post Jump Game. In the Jump Game problem, we had to calculate if we can reach the last index of the array or not. In this problem, we need to compute the minimum number of jumps.

Brute Force approach

The naive approach is to solve the problem using recursion. The base case in this recursion will occur when we reach the last index.

We will recursively call for all the elements reachable from the first element. This means we will explore all branches in the recursion stack and return the minimum number of jumps to reach the last index.

A C++ snippet of this approach is as below:

int minJumps(vector<int> &nums, int index){
    if(index >= nums.size() - 1)
        return 0;

    int jumps = INT_MAX;

    for(int index = index + 1; i <= index + nums[index]; i++)
        jumps = min(jumps, 1 + minJumps(nums, i));

    return jumps;
}

The time complexity of the above approach is O(2^N), and space complexity is O(1).

Dynamic programming

Using Dynamic programming, we can reduce the time complexity to O(N^2). The naive approach has overlapping subproblems, and their results get stored in an array. When calculating the minimum jump for the node, we check if the result is present in the stored array or not.

A C++ snippet of this approach is as below:

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> store(n);
    store[0] = 0;

    for(int i = 1; i < n; i++) {
        store[i] = INT_MAX;

        for(int j = 0; j < i; j++) {
            if(i <= nums[j] + j && store[j] != INT_MAX){
                store[i] = min(store[i], store[j] + 1);
                break;
            }
        }
    }

    return store[n - 1];
}

The time complexity of the above approach is O(N^2), and space complexity is O(n).

Optimal Greedy Approach

In this approach, we use a greedy algorithm that makes an optimal choice at each step. At any index, we determine the next steps that will move us close to the last index.

Let's check the algorithm first.

- set count, current, farthest = 0, 0, 0

- if nums[0] == 0 || nums.length == 1
  - return 0

- loop for i = 0; i < nums.length; i++
  - if nums[i] + i > farthest
    - set farthest = nums[i] + i

  - if i == current
    - increment count: count++
    - current = farthest

- for end

- return count

Let's check our solutions in C++, Golang, and Javascript.

C++ solution

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0, current = 0, farthest = 0;

        if(nums[0] == 0 || nums.size() == 1) {
            return 0;
        }

        for(int i = 0; i < nums.size() - 1; i++) {
            if(nums[i] + i > farthest) {
                farthest = nums[i] + i;
            }

            if(i == current) {
                count++;
                current = farthest;
            }
        }

        return count;
    }
};

Golang solution

func jump(nums []int) int {
    count, current, farthest := 0, 0, 0

    if nums[0] == 0 || len(nums) == 1 {
        return 0
    }

    for i := 0; i < len(nums) - 1; i++ {
        if nums[i] + i > farthest {
           farthest = nums[i] + i
        }

        if i == current {
            count++
            current = farthest
        }
    }

    return count
}

Javascript solution

var jump = function(nums) {
    let count = 0, current = 0, farthest = 0;

    if(nums[0] == 0 || nums.length == 1) {
        return 0;
    }

    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] + i > farthest) {
            farthest = nums[i] + i;
        }

        if(i == current) {
            count++;
            current = farthest;
        }
    }

    return count;
};

Let's dry run our algorithm for a given input.

Input: nums = [2, 3, 1, 1, 4]

Step 1: count = 0
        current = 0
        farthest = 0

Step 2: if nums[0] == 0 || nums.length == 1
           2 == 0 || 5 == 1
           false

Step 3: loop for i = 0; i < nums.length - 1; i++
          i < nums.length - 1
          0 <  5 - 1
          0 < 4
          true

          if nums[i] + i > farthest
             nums[0] + 0 > 0
             2 + 0 > 0
             true

             farthest = nums[i] + i
                      = 2

          if i == current
             0 == 0
             true

             count++
             count = 1

             current = farthest
                     = 2

          i++
          i = 1

Step 4: loop for i < nums.length - 1
          i < nums.length - 1
          1 <  5 - 1
          1 < 4
          true

          if nums[i] + i > farthest
             nums[1] + 1 > 2
             3 + 1 > 2
             true

             farthest = nums[i] + i
                      = 4

          if i == current
             1 == 2
             false

          i++
          i = 2

Step 5: loop for i < nums.length - 1
          i < nums.length - 1
          2 <  5 - 1
          2 < 4
          true

          if nums[i] + i > farthest
             nums[2] + 2 > 4
             1 + 2 > 4
             false

          if i == current
             2 == 2
             true

             count++
             count = 2

             current = farthest
                     = 4

          i++
          i = 3

Step 6: loop for i < nums.length - 1
          i < nums.length - 1
          3 <  5 - 1
          3 < 4
          true

          if nums[i] + i > farthest
             nums[3] + 3 > 4
             1 + 1 > 4
             false

          if i == current
             3 == 4
             false

          i++
          i = 4

Step 7: loop for i < nums.length - 1
          i < nums.length - 1
          4 <  5 - 1
          4 < 4
          false

Step 8: return count

We return the answer as 2.
Share this post!