Problem Description

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].

Intuition

The problem asks for the minimum number of jumps needed to reach the last index, where each position tells you how far you can jump ahead.

Step-by-step intuition:

1. One Jump, Many Choices: At every index, you can jump up to nums[i] steps forward. Naturally, you'd want to pick jumps that get you closer to the end as quickly as possible.

2. Greedy Exploration: Instead of simulating every possible path (which would be slow), you can use a greedy approach. Always look as far as possible in your current "jump", and when you reach the end of your current jump range, make another jump.

3. Key Insight:

   • Track for every position how far you could possibly get by the next jump (mx).
   • Advance your step counter (ans) each time you've moved as far as your current jump allows, i.e., when you finish the jump range (last == i).
   • Update your jump range (last) to the maximum position found so far.

4. Efficient Processing: You only need to scan through the array once, always tracking your jump boundary and updating when needed. This approach ensures an optimal and quick solution.

Example

Given nums = [2,3,1,1,4]:

• Start at position 0, which allows you to jump up to 2 steps ahead.
• Check positions 1 and 2; position 1 allows you to reach farther (1+3=4) than position 2 (2+1=3).
• So, your first jump takes you to position 1, from where you can jump directly to the end.

This demonstrates how finding the farthest position at each step gives an optimal path.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

The solution uses a greedy algorithm to minimize the number of jumps needed to reach the last index. Here's the detailed breakdown:

Variables

• ans: Counts the number of jumps.
• mx: Tracks the farthest index you can reach at any point during the traversal.
• last: Marks the end of your current jump range.

Algorithm

1. Iterate over the array from the first element up to the second-to-last element (nums[:-1]). There's no need to process the last index because you don't need to jump from it.

2. At every index i, calculate the farthest point you can reach so far using the expression mx = max(mx, i + nums[i]).

3. When you reach the end of the range defined by your last jump (last == i), it means you have to make a new jump:

   • Increment the jump counter with ans += 1.
   • Update the jump range with last = mx.

4. Repeat the process until the end of the array is covered.

5. Return the total number of jumps ans.

Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = mx = last = 0
        for i, x in enumerate(nums[:-1]):
            mx = max(mx, i + x)
            if last == i:
                ans += 1
                last = mx
        return ans

Complexity

• Time Complexity: O(n) — Each index is visited only once.
• Space Complexity: O(1) — Uses a constant amount of space for variables.

Pattern

This approach leverages the greedy pattern: "at each step, make the locally optimal choice (farthest reachable index) with the hope of reaching the globally optimal solution (fewest jumps)."

Example Walkthrough

Let's walk through a small example using the solution approach:

Suppose nums = [2, 1, 2, 1, 4].

Initialization:

• ans = 0 (jump count)
• mx = 0 (farthest reachable index so far)
• last = 0 (end of current jump range)

Step-by-Step:

1. Index 0: nums[0] = 2

   • You can reach up to index 0 + 2 = 2.
   • Update mx = max(0, 2) = 2.
   • Since i == last == 0, you must jump:
     • ans = 1 (first jump)
     • Update last = mx = 2

2. Index 1: nums[1] = 1

   • You can reach up to 1 + 1 = 2.
   • mx = max(2, 2) = 2.
   • Not at the end of jump range (i != last), so no jump.

3. Index 2: nums[2] = 2

   • Reach up to 2 + 2 = 4.
   • Update mx = max(2, 4) = 4.
   • At the end of current jump range (i == last == 2):
     • ans = 2 (second jump)
     • Update last = mx = 4

Now, the last covers the end of the array (last = 4, nums length is 5), so the process is done.

Result:
Minimum number of jumps to reach the end is 2 (ans = 2).

Summary Table:

This simple example illustrates the greedy choice at each step and when jumps are incremented.

Solution Implementation

Time and Space Complexity

• Time Complexity: O(n)
  The code iterates through the list nums exactly once (excluding the last element), where n is the length of nums. Each iteration performs constant-time operations.

• Space Complexity: O(1)
  Only a constant amount of extra space is used for variables (ans, mx, last, and the loop counter i). No additional data structures proportional to input size are used.

Learn more about how to find time and space complexity quickly.