DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Jump Game II

mediumGreedyMicrosoft SRE

Problem statement

You stand on index 0 of an array nums of non-negative integers. From index i you may jump forward by any distance from 1 up to nums[i]. The input is guaranteed to allow reaching the last index.

Return the minimum number of jumps needed to reach the last index.

Examples

Example 1

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

Output: 2

Explanation: Jump 0 -> 3, then 3 -> 5. One jump cannot work because index 0 reaches at most index 3.

Example 2

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

Output: 3

Explanation: Jump 0 -> 1, then 1 -> 3, then 3 -> 4.

Hints

Approach

Greedy by windows, which is really a breadth-first search where each BFS level is a contiguous range of indices.

  1. jumps = 0, window_end = 0 (the furthest index reachable with jumps jumps), furthest = 0.
  2. Scan i from 0 to the second-to-last index. Update furthest = max(furthest, i + nums[i]).
  3. When i reaches window_end, you have seen everything reachable with the current count, so one more jump is needed: jumps += 1 and window_end = furthest.
  4. Return jumps.

The scan stops before the last index because arriving there needs no further jump. Each index is visited once.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def jump(self, nums: list[int]) -> int:
jumps = window_end = furthest = 0
for i in range(len(nums) - 1):
furthest = max(furthest, i + nums[i])
if i == window_end: # used up this jump's range
jumps += 1
window_end = furthest
return jumps

Follow-up questions

  • Return the actual indices you land on, not just the count.
  • The last index might be unreachable. Return -1 in that case.

Frequently asked questions

Jumps are counted when you leave a window. If the scan included the last index and it happened to equal window_end, you would count one extra jump from a position you have already arrived at. For [0] the loop does not run at all and the answer is 0.

It is fewest-hops routing on a line: each relay, mirror or bastion reaches up to some distance ahead, and you want the smallest number of hops end to end. Recognising that BFS levels here are contiguous ranges, so no queue is needed, is the kind of simplification interviewers look for.