Jump Game II

Problem

Given a nums array where nums[i] is your max jump from index i, return the minimum number of jumps to reach the last index. You can assume you can always reach it.

Constraints

• 1 ≤ nums.length ≤ 10⁴
• 0 ≤ nums[i] ≤ 1000
• always reachable

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def jump(self, nums):
        jumps = end = far = 0
        for i in range(len(nums) - 1):
            far = max(far, i + nums[i])
            if i == end:
                jumps += 1
                end = far
        return jumps

Java

class Solution {
    public int jump(int[] nums) {
        int jumps = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currEnd) {
                jumps++;
                currEnd = farthest;
            }
        }
        return jumps;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.