Jump Game II

Jump Game II: Finding the Minimum Jumps

The Jump Game II problem builds upon the classic Jump Game challenge, where instead of determining if you can reach the last index, you aim to calculate the minimum number of jumps required to do so.

This problem requires careful planning and optimization to find the shortest path in terms of jumps.

Jump Game II

Problem Description

You are given an array nums, where each element nums[i] represents the maximum number of positions you can jump forward from index i.

Starting from index 0, determine the minimum number of jumps required to reach the last index.

Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 100

Solution Approach: Greedy Algorithm

To find the minimum number of jumps, we use a greedy approach that focuses on extending the farthest reachable position at each step.

Key Idea

  1. Keep Track of Jumps and Boundaries:

    • Use two variables:
      • current_end to mark the boundary of the current jump.
      • farthest to track the farthest position reachable with the current jumps.
    • Increment the jump count each time you reach the boundary (current_end).
  2. Iterate Through the Array:

    • At each index i, update farthest as the maximum of its current value and i + nums[i].
    • If the current index equals current_end, increment the jump count and update current_end to farthest.
  3. Stop When You Reach the Last Index:

    • Once you’ve extended beyond or reached the last index, the loop ends.

There are mainly Four  approach to solve this problem – 

  1. Recursion
  2. Dynamic Programming (Top-Down)
  3. Dynamic Programming (Bottom-Up)
  4. Greedy

1. Recursion

  • Time complexity: O(n!)
  • Space complexity: O(n)
class Solution:
    def jump(self, nums: List[int]) -> int:
        def dfs(i):
            if i == len(nums) - 1:
                return 0
            if nums[i] == 0:
                return float('inf')

            end = min(len(nums) - 1, i + nums[i])
            res = float('inf')
            for j in range(i + 1, end + 1):
                res = min(res, 1 + dfs(j))
            return res

        return dfs(0)

2. Dynamic Programming (Top-Down)

Time & Space Complexity
  • Time complexity: O(n^2)
  • Space complexity: O(n)
class Solution {
public:
    bool canJump(vector& nums) {
        unordered_map memo;
        return dfs(nums, 0, memo);
    }

private:
    bool dfs(vector& nums, int i, unordered_map& memo) {
        if (memo.count(i)) {
            return memo[i];
        }
        if (i == nums.size() - 1) {
            return true;
        }
        if (nums[i] == 0) {
            return false;
        }
        
        int end = min((int)nums.size(), i + nums[i] + 1);
        for (int j = i + 1; j < end; j++) {
            if (dfs(nums, j, memo)) {
                memo[i] = true;
                return true;
            }
        }
        memo[i] = false;
        return false;
    }
};

3. Dynamic Programming (Buttom-Up)

Time & Space Complexity
  • Time complexity: O(n^2)
  • Space complexity: O(n)

Where m is the length of the array queries and n is the length of the array intervals.

class Solution {
public:
    int jump(vector& nums) {
        int n = nums.size();
        vector dp(n, 1000000);
        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            int end = min((int)nums.size(), i + nums[i] + 1);
            for (int j = i + 1; j < end; j++) {
                dp[i] = min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
};

4. Breadth First Search (Greedy)

Time & Space Complexity
  • Time complexity: O(n)
  • Space complexity: O(1)
class Solution {
public:
    int jump(vector& nums) {
        int res = 0, l = 0, r = 0;

        while (r < nums.size() - 1) {
            int farthest = 0;
            for (int i = l; i <= r; i++) {
                farthest = max(farthest, i + nums[i]);
            }
            l = r + 1;
            r = farthest;
            res++;
        }
        return res;
    }
};

More Articles