How do you solve Jump Game II?

Use two pointers to represent the current jump's coverage (l and r). For each jump, iterate over the indices in the current coverage to find the farthest reachable index (farthest). Then update the coverage to [r+1, farthest] and increment the jump count. Repeat until the coverage reaches or passes the last index. This greedy expansion guarantees the minimum number of jumps in O(n) time.

Jump Game II

Q: What is the time complexity of Jump Game II?

O(n). Each index is visited at most once in the inner loop as the coverage range moves forward, resulting in a linear scan of the array.

Q: What pattern does Jump Game II use?

The Pattern: Greedy Algorithms (Range Expansion) The Heuristic: When minimizing the number of jumps or steps over a sequence with variable reach, track the current coverage range and greedily extend it to the farthest reachable index before incrementing the jump count, ensuring each jump covers the maximum possible distance.

Medium Greedy Algorithms

Problem

Given an array of non-negative integers nums, where each element represents the maximum jump length at that position, return the minimum number of jumps required to reach the last index of the array.

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
You can always reach the last index

Example

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

Output: 2

Starting at index 0 with value 2, the algorithm considers all reachable indices within the current jump range [0,0]. It finds the farthest reachable index in this range is index 2 (0 + nums[0] = 2). Then it jumps to the next range [1,2]. Within this new range, it finds the farthest reachable index is 4 (1 + nums[1] = 4), which is the last index. Thus, it takes 2 jumps to reach the end.

Approach

Straightforward Solution

A brute-force approach tries all possible jump sequences, exploring every reachable index recursively or via BFS, resulting in exponential or O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

At any point, the minimum number of jumps corresponds to the number of times the reachable range must be extended to cover the last index. The problem reduces to tracking the current range of indices reachable with the current number of jumps and greedily expanding to the farthest reachable index in the next jump.

Path to Optimal

Preview

The key recognition signals are 'minimum number of jumps' and 'maximum jump length at each position'. These indicate a Greedy approach because the problem can be viewed as expanding reachable ranges layer by layer, where each jump extends the coverage as far as possible…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers to represent the current jump's coverage (l and r). For each jump, iterate over the indices in the current coverage to find the farthest reachable index (farthest)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each index is visited at most once in the inner loop as the coverage range moves forward, resulting in a linear scan of the array.

Space

O(1)

Only a fixed number of variables are used to track indices and counts, with no additional data structures proportional to input size.

Pattern Spotlight

Greedy Algorithms (Range Expansion)

When minimizing the number of jumps or steps over a sequence with variable reach, track the current coverage range and greedily extend it to the farthest reachable index before incrementing the jump count, ensuring each jump covers the maximum possible distance.

Solution

Python

1class Solution:
  def jump(self, nums: list[int]) -> int:
      res = 0
      l = r = 0
5
      while r < len(nums) - 1:
          farthest = 0
          for i in range(l, r + 1):
              farthest = max(farthest, i + nums[i])
          
          l = r + 1
          r = farthest
          res += 1
      
      return res

Step-by-Step Solution

Initialize Jump Count and Coverage Pointers

3res = 0
4l = r = 0

Objective

To set up the initial state variables for counting jumps and tracking the current coverage range.

Key Insight

Starting with zero jumps and coverage pointers at the first index reflects that no jumps have been made yet and the initial coverage is just the starting position. This setup is essential for the greedy expansion logic to correctly track reachable indices and increment jumps only when coverage is extended.

Interview Quick-Check

Core Logic

Initializing both left and right pointers to zero sets the initial coverage range to the first index, representing the starting point before any jumps.

State & Boundaries

The jump count starts at zero because no jumps have been made at the start.

Expand Coverage Range Greedily Until Last Index is Reachable

To iteratively find the farthest reachable index within the current coverage and update the coverage range while counting jumps.

Return the Minimum Number of Jumps

To output the total count of jumps required to reach the last index after coverage expansion completes.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

farthest = max(farthest, i + nums[i])

Update the farthest reachable index based on the current position and its jump length.

Calculating max(farthest, i + nums[i]) finds the maximum extent reachable from the current coverage, which is critical for greedy range expansion and minimizing jumps.

Line 12 Critical

r = farthest

Update the right pointer to the farthest reachable index found.

Setting r to farthest extends the coverage to the maximum reachable index from the previous range, enabling the greedy jump that covers the largest possible distance.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does incrementing the jump count only when the current coverage range is exhausted guarantee the minimum number of jumps?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Jump Game II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Jump Game II drill

or drill a free problem

1	`class Solution:`
2	`def jump(self, nums: list[int]) -> int:`
3	`res = 0`
4	`l = r = 0`
5
6	`while r < len(nums) - 1:`
7	`farthest = 0`
8	`for i in range(l, r + 1):`
9	`farthest = max(farthest, i + nums[i])`
10
11	`l = r + 1`
12	`r = farthest`
13	`res += 1`
14
15	`return res`