DSAPrep
MediumGreedy

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index i + j where 0 <= j <= nums[i] and i + j < n.

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index 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

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It is guaranteed that you can reach nums[n - 1].
View original on LeetCode ↗

Dynamic Programming

Time O(n²)Space O(n)

dp[i] is the minimum number of jumps needed to get from index i to the last index. Computed backward, dp[i] looks at every index reachable in one jump from i and takes the best of dp[j] + 1.

class Solution:
    def jump(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        dp[-1] = 0
        for i in range(n - 2, -1, -1):
            furthest = min(i + nums[i], n - 1)
            for j in range(i + 1, furthest + 1):
                dp[i] = min(dp[i], dp[j] + 1)
        return dp[0]

Each index can scan up to nums[i] positions ahead, giving O(n²) time in the worst case and O(n) space for the dp array.

Greedy: Level-by-Level BFS

OptimalTime O(n)Space O(1)

Think of it as BFS layered by “number of jumps used so far.” cur_end marks the furthest index reachable with the jumps taken so far; farthest tracks the furthest index reachable with one more jump from anywhere in the current layer. Scan forward updating farthest; whenever the scan reaches cur_end (the boundary of the current layer), a jump is forced — commit it and move the boundary to farthest.

class Solution:
    def jump(self, nums: list[int]) -> int:
        jumps = 0
        cur_end = 0
        farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = farthest
        return jumps

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

i
2
0
3
1
1
2
1
3
4
4
farthest = 2cur_end = 0jumps = 0
1 / 6
seenresultcurrent

farthest = max(0, 0+2) = 2.

Why it’s correct: every index in the current “layer” is reachable with the same number of jumps, so the best next layer is defined by the single furthest point any of them can reach — which index in the layer produced that reach is irrelevant, since we are forced to jump exactly when the layer runs out. This is a greedy choice with no lookahead needed: taking the maximum reach of the current layer can never be beaten by taking less. Complexity: one pass, three running variables → O(n) time, O(1) space.