DSA SheetMedium
EditorialPractice

GREEDY › PART I

Jump Game II

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

reachable ranges in a jump arrayShow an array with indices 0 through 4 and values 2, 3, 1, 1, and 4. The first current range contains indices 0 through 2, which are reachable after one jump. A scan marker moves across those indices and checks their possible reaches; the value at index 1 extends farthest, all the way to index 4. The picture makes it clear that the whole current range is scanned before the next jump boundary is chosen.2311401234jump 1: current reachable range [0..2]scan marker advances across 0..2farthest reach = 4jump 2: destination range [3..4]
A jump count corresponds to a reachable range, not to one fixed landing index.

Approachscan one reachable layer at a time

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraOnly 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.

Common mistakestwo boundary errors that change the layer count

Previous · Jump Game