LeetCode Solutions Blog

Jump Game II

Number: 45

Difficulty: Medium

Paid? No

Problem Description

Given an array of non-negative integers where each element represents the maximum jump length at that position, determine the minimum number of jumps required to reach the last index. It is guaranteed that you can always reach the last index.

Key Insights

Utilize a greedy algorithm to make optimal jumps.
Track the furthest index that can be reached within the current jump range.
When the current index reaches the end of the current range, a jump is made and the range updates to the furthest reachable index.
Edge case: if the array has only one element, no jumps are needed.

Space and Time Complexity

Time Complexity: O(n) - Single pass through the array. Space Complexity: O(1) - Only a few variables are used for tracking jumps and ranges.

Solution

We use a greedy approach by iterating through the array and keeping track of:

The furthest index reachable from the current range (furthest).
The end of the current jump's range (currentEnd).
The number of jumps made (jumps).

At each iteration, we update the furthest reachable index. When the current index reaches the currentEnd, it indicates that one jump has been used and we update currentEnd to furthest. This ensures we are always making the optimal jump to cover the longest distance possible until the end of the array is reached.

Code Solutions

# Function to calculate minimum number of jumps to reach the last index
def jump(nums):
    # If the list has only one element, we're already at the destination.
    if len(nums) == 1:
        return 0
    
    n = len(nums)  # Length of the input array
    jumps = 0     # To count the number of jumps required
    currentEnd = 0  # The end of the current range that can be reached
    furthest = 0  # The furthest index that can be reached from the current range
    
    # Iterate till the second last element because we don't need to jump from the last element
    for i in range(n - 1):
        # Update the furthest index reachable from index i
        furthest = max(furthest, i + nums[i])
        # If we have reached the end of the current jump range
        if i == currentEnd:
            jumps += 1            # Increase the jump count as we make a jump
            currentEnd = furthest # Update the currentEnd to the furthest reachable index
    return jumps

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