What is the brute force approach and complexity for Jump Game?

From each index, try every jump length one by one with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Jump Game?

Scan left to right and keep the farthest index you can reach so far with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Jump Game?

Look for key signals in the prompt: "jump at most nums[i] steps" indicates From index `i` you can land on any of up to `nums[i]` spots after it. Every jump goes right, never left.; "reach the last index" indicates We only need a yes or no, so the reachable block is enough. We do not need the routes.; "start on index 0" indicates The reachable indexes start at 0 and grow to the right with no holes..

Jump Game

Medium·LeetCode #55Basic Anchor

LeetCode

Jump:

30-Second Mental ModelReachability (farthest reach)

Complexity:O(2^N)→O(N)

Key Insight

Keep one number, far: the farthest index we know we can reach. Walk i from left to right. If i is past far, it cannot be reached, so return false. Otherwise i is reachable and extends the block to i + nums[i], so set far = max(far, i + nums[i]).

Core Validity Invariant

Index i is reachable only if i ≤ far, so one comparison between i and far decides whether the walk is stuck.

Problem

You start on index 0 of an array nums. Each number is the longest jump you can make from that index: from index i you may land on any index from i + 1 up to i + nums[i], as long as you stay inside the array.

Return true if you can reach the last index, and false otherwise.

Input

An array of integers nums. nums[i] is the furthest forward jump from index i.

Output

true if the last index can be reached from index 0, otherwise false.

Example 1

Input: nums = [2, 3, 1, 1, 4]

Output: true

Jump 1 step from index 0 to index 1 (its value is 3), then jump up to 3 steps from there to the last index.

Example 2

Input: nums = [3, 2, 1, 0, 4]

Output: false

No jump from index 0, 1, 2 or 3 gets past index 3, and index 3 holds 0. So index 4 is never reached.

Constraints

• 1 ≤ nums.length ≤ 10^4
• 0 ≤ nums[i] ≤ 10^5

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Do I need the exact route, or only whether some route reaches the end?
2.
If I stand on an index that holds 0, am I always stuck? What if I never have to land on it?
3.
Suppose every index up to some point is reachable. Which index is the furthest one I can be sure of?
4.
If index i is reachable, which new indexes does it make reachable?
5.
Can one number and one pass answer the question, without a table?

Brute force approach

Idea

From index i, try each jump length len from 1 up to nums[i]. Land on i + len and ask the same question from there. If any choice reaches the last index, return true. If every choice fails, return false.

Thinking process

1
I do not know which jump length to pick, so I try them one by one.
2
On [2, 3, 1, 1, 4], from index 0 I first try landing on index 1. Index 1 holds 3, so from there I try 1, 2 or 3 steps.
3
Jumping 3 steps from index 1 lands on index 4, the last index. This path works, so the answer is true.
4
If every path from index 0 had failed, the answer would be false.

Code & Implementation

brute.cpp

class Solution {
public:
    bool canJump(vector<int>& nums) {
        return canFrom(nums, 0);
    }

private:
    // Can we reach the last index when standing on index i?
    // Try every jump length from i, one after another.
    bool canFrom(vector<int>& nums, int i) {
        int n = nums.size();
        if (i == n - 1) return true;
        for (int len = 1; len <= nums[i] && i + len < n; len++) {
            if (canFrom(nums, i + len)) return true;
        }
        return false;
    }
};

Complexity

Time O(2^N)Space O(N)

Every route is a list of landing spots that only move forward, so there are at most 2^(N−1) routes. The recursion goes at most N calls deep, which is the O(N) space. With N = 10^4 this never finishes.

Better approach

Why brute force is slow

The brute force walks every route. Many routes land on the same index, and the work after that index is done again on every one of them.

What repeated work are we doing?

Whether index j can be reached is worked out again on every route that lands on j.

What information can we reuse?

Store one true or false per index in reach. After that, each index only looks at the table, not at the routes.

New approach

Idea

Let reach[i] be true if index i can be stood on. Index i is reachable when some earlier index j is reachable and j + nums[j] ≥ i, which means j can jump to i. Fill the table from left to right. The answer is reach[n − 1].

Thinking process

1
The brute force keeps asking "can I finish from here?" for the same index again and again.
2
Ask a simpler question for each index instead: can I stand on it at all?
3
On [2, 3, 1, 1, 4]: reach[0] is true. Index 1 is reached because 0 + 2 ≥ 1. Index 4 is reached because 1 + 3 ≥ 4.
4
Each entry only looks at entries before it, so one left-to-right pass fills the whole table.

Code & Implementation

better.cpp

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        // reach[i] = true if index i can be stood on (reached from index 0).
        vector<bool> reach(n, false);
        reach[0] = true;
        for (int i = 1; i < n; i++) {
            // Index i is reachable if some reachable j < i jumps at least as far as i.
            for (int j = 0; j < i; j++) {
                if (reach[j] && j + nums[j] >= i) {
                    reach[i] = true;
                    break;
                }
            }
        }
        return reach[n - 1];
    }
};

Complexity

Time O(N²)Space O(N)

Index i checks up to i earlier indexes, so about N²/2 checks. With N = 10^4 that is about 5·10^7, which runs fine in C++, but the next idea needs only one pass.

Optimized approach

Idea

Start from brute force

Brute force tries every jump length from every index. The table asks, for each index, about every earlier index. Both redo work that never changes the answer.

Find the repeated work

Most earlier indexes add nothing new. For index i, the only thing that matters is the farthest index that any reachable spot before it can jump to.

Define the state — what variables do I need?

far: The farthest index we know we can reach. Every index from 0 to `far` is reachable.
i: The index we are checking now. It is reachable only if it is at most `far`.

Define validity

Index i is reachable only if i ≤ far, so one comparison between i and far decides whether the walk is stuck.

Define the transitions — when does each pointer move, and why is it safe?

i > far

return false

No index before i jumps as far as i, so the walk can never get past far.

i ≤ far

far = max(far, i + nums[i])

Index i is reachable, so from it we can reach every index up to i + nums[i]. The block grows to that end.

after the loop

return far ≥ n − 1

If the loop finished, every index was inside the block. The last index is reachable exactly when far covers it.

What does the current window add to the answer?

There is no running total to collect. Each step either grows far or shows the walk is stuck. The answer is far ≥ n − 1 at the end.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int far = 0;  // farthest index we know we can reach
        for (int i = 0; i < n; i++) {
            // i is past the reachable block, so no earlier index jumps this far.
            if (i > far) return false;
            far = max(far, i + nums[i]);
        }
        return far >= n - 1;
    }
};

Complexity

Time O(N)Space O(1)

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	From each index, try every jump length one by one	O(2^N)	O(N)
Better	For each index, check whether a reachable earlier index can jump to it	O(N²)	O(N)
Optimal	Scan left to right and keep the farthest index you can reach so far	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“jump at most nums[i] steps”From index `i` you can land on any of up to `nums[i]` spots after it. Every jump goes right, never left.
“reach the last index”We only need a yes or no, so the reachable block is enough. We do not need the routes.
“start on index 0”The reachable indexes start at 0 and grow to the right with no holes.

Reachable indexes form one block [0 … far]+far = max(i + nums[i])+stuck when i > far→Reachability (farthest reach)

This is the anchor of the reachability sub-pattern: the whole answer depends on one number, the farthest index reached so far. Jump Game II keeps the same frontier but counts rounds. Jump Game III breaks the rule, because a jump can also go left, so the reachable indexes are no longer one block that starts at the beginning.

Don't make this mistake

Pattern confusion: stopping at every zero

✗ if (nums[i] == 0) return false;

✓ if (i > far) return false;

A zero is a dead end only if the walk has to stop on it. On [2, 0, 0] you jump 2 steps from index 0 straight to index 2, the last index, so the answer is true. The wrong check returns false at index 1. What matters is whether index i is inside the block (i ≤ far), not whether its value is 0.

Updating far before checking i

✗ far = max(far, i + nums[i]); if (i > far) return false;

✓ if (i > far) return false; far = max(far, i + nums[i]);

After the update, far is at least i + nums[i], which is at least i. So i > far can never be true, and the check never fires. On [3, 2, 1, 0, 4] the wrong version returns true, but the answer is false: index 4 is past far = 3.

Edge case: a single element

✗ if (nums[0] == 0) return false;

✓ No special case: the loop handles n = 1.

With nums = [0] you already stand on the last index, so the answer is true. The loop starts at index 0, which is also the last index, so it returns true without any jump.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture