{x}
blog image

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

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 <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Solution Explanation: Jump Game II

This problem asks for the minimum number of jumps required to reach the last index of an array, where each element represents the maximum jump length from that index. A greedy approach provides an efficient solution.

Approach: Greedy Algorithm

The core idea is to iteratively find the farthest reachable index from the current position. We maintain three variables:

  • ans: Counts the number of jumps made.
  • mx: Tracks the farthest index reachable from the current jump's starting point.
  • last: Keeps track of the last reached index after a jump.

The algorithm iterates through the array (except for the last element). In each iteration:

  1. Update mx: Calculate the farthest reachable index from the current position (i + nums[i]) and update mx if this new reach is farther.

  2. Check Jump Boundary: If the current index i equals last, it signifies that we've reached the boundary of the previous jump. This means we need to make another jump.

  3. Update Jump Information: If a jump is needed:

    • Increment ans.
    • Update last to mx to reflect the new reachable boundary.

Finally, ans will hold the minimum number of jumps required.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = mx = last = 0
        for i, x in enumerate(nums[:-1]): # Iterate up to second-to-last element
            mx = max(mx, i + x) # Update farthest reachable index
            if last == i: # Reached the boundary of the previous jump?
                ans += 1  # Make a jump
                last = mx # Update the boundary of the new jump
        return ans

The code in other languages (Java, C++, Go, TypeScript, Rust, C#, C, PHP) follow the same logic, only differing in syntax and data structures. They all maintain the three variables (ans, mx, last) and use the same iterative approach for finding the minimum jumps.

Example Walkthrough (nums = [2,3,1,1,4])

  1. Initially: ans = 0, mx = 0, last = 0.
  2. i = 0, x = 2: mx = max(0, 0 + 2) = 2. last == i (0 == 0), so ans = 1, last = 2.
  3. i = 1, x = 3: mx = max(2, 1 + 3) = 4. last != i (2 != 1).
  4. i = 2, x = 1: mx = max(4, 2 + 1) = 4. last != i (2 != 2).
  5. i = 3, x = 1: mx = max(4, 3 + 1) = 4. last == i (2 == 2), so ans = 2, last = 4.
  6. Loop ends because i has reached the second-to-last element.
  7. The function returns ans = 2.

This shows that the minimum number of jumps needed is 2.