Problem Statement

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 always reach nums[n - 1].

Additional information

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It's guaranteed 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

1D Dynamic Programming

Intuition

To find the minimum number of jumps to reach the end, we can build an array that stores the minimum jumps required to reach every single index.

We initialize a dp array where dp[i] represents the minimum jumps to reach index i. We fill it with infinity initially, except for dp[0] = 0 (since we start there, it takes 0 jumps to reach it).

Then, we iterate through the array. For every index i, we look at how far we can jump (nums[i]). We update all the reachable future indices: if jumping from i provides a strictly smaller jump count than the previously recorded value for that future index, we overwrite it.

Algorithm

1. Initialize n = len(nums).
2. If n == 1, return 0 immediately.
3. Create a dp array of size n filled with infinity (float("inf")).
4. Set dp[0] = 0.
5. Loop i from 0 to n - 1.
6. Loop j from 1 to nums[i].
7. Check if i + j < n (to prevent out-of-bounds errors).
8. Update the future index: dp[i + j] = min(dp[i + j], dp[i] + 1).
9. Return the final element dp[n - 1].

def jump(nums: list[int]) -> int:
    n = len(nums)
    if n == 1:
        return 0
        
    dp = [float("inf")] * n
    dp[0] = 0
    
    for i in range(n):
        # We can jump up to nums[i] steps forward
        for j in range(1, nums[i] + 1):
            if i + j < n:
                # The minimum jumps to reach i+j is either its current best, or 1 jump from i
                dp[i + j] = min(dp[i + j], dp[i] + 1)
                
    return dp[n - 1]

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: For every element in the array of size N, we might iterate through up to N subsequent elements. This nested loop structure results in a quadratic runtime, which can be slow for large inputs.

• Space complexity: O(N)

• Reason: The dp array stores N integer values.

Greedy BFS Algorithm - Optimal

Intuition

Instead of updating every single future step, we can think of this problem like a level-by-level Breadth-First Search (BFS).

Imagine we are standing at index 0. We can jump a certain distance. Everything within that distance forms our "current window" (or BFS level). We need to figure out the absolute furthest we can jump if we were to take off from anywhere inside this current window.

As we iterate through our current window, we continuously track the farthest index reachable. The moment our loop reaches the end of our current_end window, it means we are forced to make a jump! We increment our jump counter, and our new window expands to whatever the farthest point was. We repeat this until our window covers the final index.

Algorithm

1. Initialize three integers: jumps = 0, current_end = 0, and farthest = 0.
2. Iterate i from 0 to len(nums) - 2. We stop at the second-to-last element because if we reach the last element, we are already there and don't need to jump again.
3. Continuously update farthest = max(farthest, i + nums[i]). This explores all possibilities within the current jump range to find the optimal launchpad.
4. If i == current_end:

• It means we have explored the entire current jump window and must commit to a jump.
• Increment jumps += 1.
• Update current_end = farthest to mark the boundary of our next jump window.
• Early Exit (Optional): If current_end >= len(nums) - 1, we can break out of the loop early.

5. Return jumps.

def jump(nums: list[int]) -> int:
    jumps = 0
    current_end = 0
    farthest = 0
    
    # We don't need to iterate the last element, because jumping from the last element is not needed
    for i in range(len(nums) - 1):
        # Greedily find the absolute furthest we can reach from our current position
        farthest = max(farthest, i + nums[i])
        
        # If we have reached the end of the current jump window, we must jump!
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # If our new window reaches or exceeds the destination, we are done
            if current_end >= len(nums) - 1:
                break
                
    return jumps

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the array exactly one time. The operations inside the loop are simple constant time O(1) assignments and comparisons.

• Space complexity: O(1)

• Reason: We only use three integer variables (jumps, current_end, farthest) to track the implicit BFS levels, eliminating the need for an O(N) Dynamic Programming array.