123.Jump Game

MediumBlind 75Greedy · 2/8

Problem

You are given an integer array nums. You start at index 0, and nums[i] is the maximum jump length from index i (you may jump any distance from 0 to nums[i]).

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

Examples

Input:  nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step to index 1, then 3 steps to the last index.

Input:  nums = [3,2,1,0,4]
Output: false
Explanation: Every path lands on index 3, whose jump length is 0, so index 4 is unreachable.

Input:  nums = [0]
Output: true
Explanation: We already stand on the last index.

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

💡 Key Insight

The set of reachable indices is always a contiguous prefix [0, farthest]: if you can reach index i, you can reach every index before it too. So we only need to track farthest, the furthest index reachable so far. Walking left to right, if we ever stand on an index beyond farthest, we are stuck; otherwise extend farthest with i + nums[i].

Brute Force Recursion

TimeO(2^n) in the worst caseSpaceO(n)

Intuition

From index i, try every jump length 1..nums[i] and recursively ask whether the landing index can reach the end. This explores every path and is exponential because the same index is re-solved many times.

Algorithm

canReach(i): if i >= n - 1 return true.
For step from nums[i] down to 1: if canReach(i + step) return true.
Return false.

Visualization

nums = [3,2,1,0,4]
canReach(0) -> try 3: canReach(3) stuck (nums[3] = 0)
            -> try 2: canReach(2) -> canReach(3) stuck again
            -> try 1: canReach(1) -> canReach(3), canReach(2) -> ... all stuck
index 3 is solved many times -> exponential blow-up

Code

java

class Solution {
    public boolean canJump(int[] nums) {
        return canReach(nums, 0);
    }

    private boolean canReach(int[] nums, int i) {
        if (i >= nums.length - 1) {
            return true;
        }
        // try longer jumps first; any success is enough
        for (int step = nums[i]; step >= 1; step--) {
            if (canReach(nums, i + step)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(2^n) in the worst case — overlapping subproblems are recomputed.
Space: O(n) — recursion depth.

Bottom-Up DP

TimeO(n²)SpaceO(n)

Intuition

Let good[i] be true if the last index is reachable from i. The last index is good by definition. Working right to left, i is good if any index in [i + 1, i + nums[i]] is good. Each index is solved once.

Algorithm

good[n - 1] = true.
For i from n - 2 down to 0: scan j in i + 1 .. min(n - 1, i + nums[i]); if any good[j], set good[i] = true.
Return good[0].

Visualization

i	nums[i]	range checked	good[i]
4	4	—	true
3	0	none	false
2	1	3	false
1	2	2..3	false
0	3	1..3	false

nums = [3,2,1,0,4] → good[0] = false.

Code

java

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] good = new boolean[n];
        good[n - 1] = true;
        for (int i = n - 2; i >= 0; i--) {
            int furthest = Math.min(n - 1, i + nums[i]);
            for (int j = i + 1; j <= furthest; j++) {
                if (good[j]) {
                    good[i] = true; // can jump to a good index
                    break;
                }
            }
        }
        return good[0];
    }
}

Complexity

Time: O(n²) — each index may scan up to n successors.
Space: O(n) — the good array.

GreedyOptimal

TimeO(n)SpaceO(1).

Intuition

Notice in the DP that we only ever need the leftmost good index: i is good iff i + nums[i] >= leftmostGood. Scanning right to left and moving a goal pointer to i whenever i can reach it gives O(n). Equivalently, scan left to right tracking farthest; this is the version below.

Algorithm

farthest = 0.
For each i from 0 to n - 1:
- If i > farthest, return false (this index is unreachable).
- farthest = max(farthest, i + nums[i]).
- If farthest >= n - 1, return true.
Return true.

Dry Run

flowchart LR
    A["i=0, nums=3<br/>farthest = 3"] --> B["i=1, nums=2<br/>farthest = 3"]
    B --> C["i=2, nums=1<br/>farthest = 3"]
    C --> D["i=3, nums=0<br/>farthest = 3"]
    D --> E{"i=4 > farthest 3?"}
    E -->|"yes"| F["return false"]

nums = [2,3,1,1,4]
i=0: farthest = 2
i=1: farthest = max(2, 1+3) = 4 >= 4 -> return true

Code

java

class Solution {
    public boolean canJump(int[] nums) {
        int farthest = 0; // furthest index reachable so far
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) {
                return false; // there is a gap we cannot cross
            }
            farthest = Math.max(farthest, i + nums[i]);
            if (farthest >= nums.length - 1) {
                return true;
            }
        }
        return true;
    }
}

Complexity

Time: O(n) — single pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force Recursion	O(2^n)	O(n)
Bottom-Up DP	O(n²)	O(n)
Greedy	O(n)	O(1)

Common Pitfalls

Treating nums[i] as the exact jump length — it is the maximum; any shorter jump is allowed.
Forgetting the single-element array: you are already at the last index, so the answer is true.
Checking i > farthest after updating farthest — an unreachable index must not contribute its own jump.
Overflow is not an issue here (i + nums[i] <= 1.1 · 10^5), but in similar problems with large values use long.