Facebook Pixel

45. Jump Game II

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)."

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

Indexnums[i]Reachablemxlastans
022221
112221
224442

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

Solution Implementation

1from typing import List
2
3class Solution:
4    def jump(self, nums: List[int]) -> int:
5        jumps = 0       # Number of jumps made so far
6        farthest = 0    # The farthest index we can reach in the current jump
7        end = 0         # The end index of the current jump range
8
9        # Iterate through the array, except the last element
10        for i, num in enumerate(nums[:-1]):
11            # Update the farthest position reachable from current or previous steps
12            farthest = max(farthest, i + num)
13
14            # If we have reached the end of the range for the current jump
15            if i == end:
16                jumps += 1          # Make a jump
17                end = farthest      # Update the end of the next jump range
18
19        return jumps
20
1class Solution {
2    public int jump(int[] nums) {
3        // ans: Minimum number of jumps needed to reach the end
4        // farthest: The farthest index that can be reached so far
5        // end: The end of the current jump range
6        int ans = 0;
7        int farthest = 0;
8        int end = 0;
9
10        // Loop through the array (but not including the last element)
11        for (int i = 0; i < nums.length - 1; ++i) {
12            // Update the farthest index we can reach from current position
13            farthest = Math.max(farthest, i + nums[i]);
14            // If we've reached the end of the current jump range
15            if (i == end) {
16                ans++;              // Make a jump
17                end = farthest;     // Set new end for the next jump
18            }
19        }
20        return ans;
21    }
22}
23
1class Solution {
2public:
3    int jump(std::vector<int>& nums) {
4        int jumps = 0;      // Number of jumps made so far
5        int farthest = 0;   // The farthest index reachable at the current step
6        int end = 0;        // The end of the range for the current jump
7
8        // We do not need to consider the last position, because we never need to jump from it
9        for (int i = 0; i < nums.size() - 1; ++i) {
10            // Update the farthest we can reach from current position
11            farthest = std::max(farthest, i + nums[i]);
12
13            // If we've reached the end of the current jump,
14            // increase the jump count and set new range boundary
15            if (i == end) {
16                ++jumps;
17                end = farthest;
18            }
19        }
20        return jumps;
21    }
22};
23
1/**
2 * Finds the minimum number of jumps needed to reach the last index of the array.
3 * Each element in the array represents the maximum jump length at that position.
4 * @param nums Array of non-negative integers
5 * @returns Minimum number of jumps needed to reach the end
6 */
7function jump(nums: number[]): number {
8    // answer: stores number of jumps
9    // farthest: the farthest index we can reach in current iteration
10    // currentEnd: end of current jump range
11    let answer = 0, farthest = 0, currentEnd = 0;
12
13    // No need to consider the last element since we stop one step before reaching it
14    for (let i = 0; i < nums.length - 1; ++i) {
15        // Update the farthest position that can be reached
16        farthest = Math.max(farthest, i + nums[i]);
17
18        // If we've reached the end of the current jump range
19        if (i === currentEnd) {
20            answer++; // Increment jump count
21            currentEnd = farthest; // Set new range end
22        }
23    }
24    return answer;
25}
26

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More