Blind 75 Visualized

#62 · Greedy

Jump Game

Each element of the array is the maximum jump length from that position. Starting at the first index, can you reach the last index?

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Farthest-reach frontier

The set of indices reachable from the start is always a prefix [0, farthest]: if you can reach index k you can reach everything before it by shorter jumps along the way. So the only state needed is the single number farthest.

Memory layout

One integer.

OperationCost
timeO(n)
spaceO(1)

Reachability table

good[i] says whether the end can be reached from i. It is true if some index within nums[i] steps is good. Filling it from the right needs each position to look at up to nums[i] successors.

Memory layout

A boolean per index.

OperationCost
time / spaceO(n²) / O(n)

Why it fits

  • Reachable positions form a contiguous prefix, because any jump may be shortened. That collapses the whole question to "how far can I get?".
  • Extending that frontier at each index is a greedy step that never needs undoing: a larger reach is always at least as good as a smaller one.
  • An index beyond the frontier is a certificate of failure: nothing before it can jump that far.

Why alternatives degrade

Always jump the maximum distance:
For 2, 3, 1, 1, 4 jumping 2 from index 0 lands on 1 and works, but for 2, 0, 0 the maximum jump lands on a 0. A fixed greedy choice of the jump itself is wrong; tracking the reachable range is right.
Plain DFS over jumps:
It re-explores the same dead indices through many routes, which is exponential.
Shortest path (BFS) over indices:
It is correct but visits O(n²) edges for no benefit when only reachability is needed.

Four approaches, from naive to production

1 · beginner

Backtracking over every jump

time O(2ⁿ)space O(n)

From index i try each jump length from 1 to nums[i] and recurse; succeed if any route reaches the last index.

bool canJump(vector<int>& nums) {
    int last = nums.size() - 1;
    function<bool(int)> reach = [&](int i) -> bool {
        if (i >= last) return true;
        for (int step = 1; step <= nums[i]; step++) {
            if (reach(i + step)) return true;
        }
        return false;
    };
    return reach(0);
}

Flaws & bottlenecks

  • The same dead index is reached through many routes and re-explored each time.
  • Exponential in the worst case (for example a long array of 1s ending in a 0 after many large values).
  • Recursion depth up to n.

Interviewer cross-questions

Why is it exponential?

Say: With large values every index can jump to many others, so the number of distinct routes grows exponentially, and nothing remembers that an index already failed.

What is the minimal change to avoid the repeats?

Say: Remember, for every index, whether it can reach the end (memoisation); a failing index is then searched only once.

Does the order of the jumps matter?

Say: For correctness no. Trying the longest jump first often finds a success sooner, but it does not change the worst case.

2 · intermediate

Memoised search

time O(n²)space O(n)

Same search, but store for each index whether it succeeded or failed, so each index is explored at most once.

bool canJump(vector<int>& nums) {
    int last = nums.size() - 1;
    vector<int> memo(nums.size(), -1);
    function<bool(int)> reach = [&](int i) -> bool {
        if (i >= last) return true;
        if (memo[i] != -1) return memo[i];
        bool ok = false;
        for (int step = 1; step <= nums[i]; step++) {
            if (reach(i + step)) {
                ok = true;
                break;
            }
        }
        memo[i] = ok;
        return ok;
    };
    return reach(0);
}

Flaws & bottlenecks

  • Still O(n²): each index may try up to nums[i] jumps.
  • Recursion depth up to n.
  • Needs a tri-state memo (unknown, true, false).

Interviewer cross-questions

Why is it O(n²)?

Say: There are n states and each loops over up to n − i successors, so about n²/2 checks in the worst case.

Why must failures be remembered?

Say: A failing index is the expensive case: its whole subtree is searched without success. Without a stored false it would be searched again every time it is reached.

Can you avoid the loop at every index?

Say: Yes: reachable positions form a prefix, so tracking only the farthest reachable index answers the question in O(n).

3 · advanced

Bottom-up table from the end

time O(n²)space O(n)

good[n − 1] is true. Going from the right, index i is good if any index in i + 1 … i + nums[i] is good. The answer is good[0].

bool canJump(vector<int>& nums) {
    int n = nums.size();
    vector<bool> good(n, false);
    good[n - 1] = true;
    for (int i = n - 2; i >= 0; i--) {
        int furthest = min(i + nums[i], n - 1);
        for (int j = i + 1; j <= furthest; j++) {
            if (good[j]) {
                good[i] = true;
                break;
            }
        }
    }
    return good[0];
}

Flaws & bottlenecks

  • Quadratic when many large jumps exist and the good indices are far away.
  • Uses O(n) memory for a yes/no per index.
  • Does not exploit the prefix structure of the reachable set.

Interviewer cross-questions

Why work from the right?

Say: good[i] depends on later indices, so computing from the end guarantees they are decided.

How can you speed up the inner loop?

Say: Keep only the leftmost good index seen so far: i is good exactly when i + nums[i] ≥ that index. That gives O(n) time and O(1) space (the leftmost-good-index greedy).

What does the table tell you beyond the answer?

Say: It says from which positions the end is reachable, which you could use to reconstruct a route.

4 · expert

Greedy: farthest reachable index

time O(n)space O(1)

Scan once keeping farthest, the largest index reachable so far. If the scan reaches an index beyond farthest, fail; otherwise update farthest with i + nums[i], and succeed as soon as farthest covers the last index.

bool canJump(vector<int>& nums) {
    int farthest = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > farthest) return false;
        farthest = max(farthest, i + nums[i]);
        if (farthest >= (int)nums.size() - 1) return true;
    }
    return true;
}

Flaws & bottlenecks

  • It answers yes/no only; counting the minimum number of jumps needs a related but different greedy (Jump Game II).
  • The reasoning (reachable set is a prefix) is subtle to articulate.
  • An off-by-one in the comparisons (> vs ≥) silently gives wrong results.

Interviewer cross-questions

Why is the reachable set a prefix?

Say: If you can reach index k you can reach every index before it as well: take the same route but shorten the last jump so it lands earlier. So only the maximum matters.

Why can we stop when i > farthest?

Say: Every index before i can reach at most farthest < i, so index i is unreachable, and nothing beyond i can be reached either, because to get there you must pass through an index ≤ farthest.

How would you find the minimum number of jumps?

Say: Keep the end of the current jump window and the farthest reach seen within it; when the window ends, count one more jump and extend the window to the farthest reach. It is still O(n) (Jump Game II).

Synchronized code walkthrough

Showing: Backtracking over every jump — shares the player above; click any step to jump.

bool canJump(vector<int>& nums) {
    int last = nums.size() - 1;
    function<bool(int)> reach = [&](int i) -> bool {
        if (i >= last) return true;
        for (int step = 1; step <= nums[i]; step++) {
            if (reach(i + step)) return true;
        }
        return false;
    };
    return reach(0);
}