algoadvance

You are given an array of non-negative integers representing the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps.

Write a function jump(nums: List[int]) -> int that takes an array nums and returns the minimum number of jumps required to reach the last index.

Example:

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.

Note:

Clarifying Questions

  1. Can the array contain a single element? Yes, in such case, no jump is needed and the output should be 0.

  2. Does the input array guarantee that the last index is reachable from the first index? Yes, we can assume that we can always reach the last index.

Strategy

The idea is to use a greedy approach to solve this problem. We maintain a current end which tells us the farthest point that can be reached with the current number of jumps, and a farthest point which tells us the farthest point that can be reached with the next jump.

  1. Initialize jumps to 0, current_end to 0, and farthest to 0.
  2. Iterate over each index i of the array except the last one:
    • Update farthest to be the maximum of farthest and i + nums[i].
    • If we have reached the current_end, increment jumps and update current_end to farthest.
  3. Return the number of jumps.

By the end of the iteration, jumps will hold the minimum number of jumps needed to reach the last index.

Code

from typing import List

def jump(nums: List[int]) -> int:
    if len(nums) == 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        
        # if we have come to the end of our possible current jump
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # if the farthest we can currently reach includes the last element
            if current_end >= len(nums) - 1:
                break
    
    return jumps

# Example usage:
print(jump([2, 3, 1, 1, 4]))  # Output: 2

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of elements in the array. This is because we make a single pass through the array to determine the number of jumps. The space complexity is O(1) since we are only using a constant amount of extra space.

Try our interview co-pilot at AlgoAdvance.com