Jump Game II — Editorial

Opening the reading…

Intuitionwhy one scan finds the minimum number of jumps

After zero jumps, you are at index 0. After one jump, you can reach every index from 1 through nums[0], and after two jumps, you can reach a larger interval formed by all of those positions. The important fact is that indices reachable with the same number of jumps form a current range, so you do not need to decide the exact landing position immediately.

Scan every index in the current range and record the farthest position any of them can reach. When the scan arrives at the end of that range, one more jump is unavoidable, and the farthest recorded position becomes the end of the next range. Choosing that farthest boundary cannot hurt: every other landing point in the current range reaches no farther, so none can create a better next layer.

A jump count corresponds to a reachable range, not to one fixed landing index.

Approachscan one reachable layer at a time

Set jumps, curEnd, and curFarthest to zero. The initial range contains index 0, and these variables describe the current number of jumps, its boundary, and the best boundary for the next jump.

Scan i from 0 through n - 2, because the destination never needs to launch another jump and including it could create an unnecessary boundary update.

For each i, update curFarthest with i + nums[i]. This preserves the best next boundary seen across the entire current range; replacing it instead of taking the maximum can lose reach from an earlier index.

When i equals curEnd, increment jumps and set curEnd to curFarthest. You have finished examining every position reachable with the old jump count, so another jump is necessary and the farthest candidate gives the widest next range.

Return jumps after the scan. The input guarantees that the destination is reachable, so every boundary that matters is eventually extended to or beyond index n - 1.

Complexityone pass and constant working memory

MEASURE	BOUND	WHY
Time	O(n)	The loop examines each index from 0 through n - 2 once, and each iteration performs constant-time arithmetic and comparison. No index is rescanned when a jump boundary changes, so the total work is linear.
Space	O(1) extra	Only jumps, curEnd, curFarthest, and a loop index are stored. The returned integer is the required output and is not working memory, so it is excluded; the bound stays constant even for the worst input shape.

Here n is the length of nums.

Annotated solutionC++ · greedy range scan · the version to write from memory

CPPGreedy scan that counts a jump whenever the current reachable range ends.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return 0;

        int jumps = 0;
        int curEnd = 0;
        int curFarthest = 0;

        for (int i = 0; i < n - 1; ++i) {
            curFarthest = max(curFarthest, i + nums[i]);

            if (i == curEnd) {
                ++jumps;
                curEnd = curFarthest;
            }
        }

        return jumps;
    }
};

The order of the two operations inside the loop is the core of the solution. First include nums[i] in curFarthest, then check whether i is the current boundary. At the boundary, the index you just processed is still part of the current range, so its jump must be considered before choosing the next range. The loop stops at n - 2 because reaching the last index is enough.