Jump Game II

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.

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

Watch how farthest grows while cur_end stays put, and how a jump is forced exactly when the scan reaches cur_end.

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.