Difficulty: MediumGreedy

Jump Game

Problem in Plain English

Given an array where each element caps how far you can jump forward from that position, decide whether the last index is reachable starting from the first index.

Problem Statement

Given a nonempty integer array nums, start at index 0. From index i, you may jump forward by any number of positions from 1 through nums[i]; the value is a maximum, not a required distance. Return whether you can reach the last index. You need not return a path or minimize the number of jumps.

Constraints

$1 \leq n = \mathrm{nums.length} \leq 10^4$ .
$0 \leq \mathrm{nums}[i] \leq 10^5$ .

Examples

Example 1

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

Jump one step from index 0 to 1, then three steps to index 4. The first jump need not use the full value 2.

Example 2

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

Indices 0, 1, and 2 can reach at most index 3. Its zero cannot extend reachability, so index 4 stays unreachable.

Example 3

Input: nums = [0]
Output: true

The starting index is already the last index; no jump is required even though the only value is zero.

Example 4

Input: nums = [2, 0, 0]
Output: true

Index 0 jumps directly to index 2, skipping the zero at index 1. A zero alone does not imply failure.

Intuition

Reachable positions form a continuous prefix because any jump distance up to the maximum is allowed. In Example 1, index 0 with value 2 makes indices 1 and 2 reachable; reachable index 1 then extends that prefix through index 4. We can either explore the choices and remember each result, or merge every reachable choice into one farthest frontier. A zero blocks progress only when no earlier reachable position can jump past it.

Approaches

Memoized Recursion

Solution Details

Reveal Memoized Recursion: intuition, complexity, and code

Intuition

Explore each possible forward landing and memoize whether it can finish. Forward-only jumps make the dependency graph acyclic: once a position has been solved, every later query can reuse its answer. The published implementation represents recursive calls with explicit frames so a 10000-position chain does not overflow a language call stack.

Step-by-Step Logic

Mark the last index successful and every other memo entry unknown. Push a frame holding position 0 and its next candidate 1; in Example 1 the last index is 4.
For the top frame, cap its last landing at the last index. If its next candidate is unknown, push that child frame and leave the parent candidate unchanged until the child returns. Example 1 descends through positions 0, 1, 2, and 3.
If the child is successful, mark the current position successful and pop its frame. If the child failed, advance the candidate by one. When every legal child fails, memoize failure and pop the frame.
Continue until no frames remain, then return the memoized answer at index 0. Example 1 finds known-success index 4 from 3 and propagates success through 2, 1, and 0.

Why It Works

The last index succeeds without a jump. For any earlier position, a successful legal child supplies a complete path, so returning success is sound. Conversely, every path must begin with one of the landings from the next index through the capped endpoint. If all those children fail, no path can finish. All children have larger indices, so there are no cycles; depth-first frames solve each child before its parent uses that result. Memoized results therefore equal reachability by backward induction, and the root result answers the original question. Keeping the parent candidate unchanged while the child is pending ensures its result is actually examined.

Dry Run

Memoized Recursion: variable states at each step
action	frame stack positions	top candidate	memo change
initialize	`[0]`	`1`	`memo[4] = 1`, others `-1`
push unknown child of `0`, endpoint `2`	`[0, 1]`	`2`	none
push unknown child of `1`, endpoint `4`	`[0, 1, 2]`	`3`	none
push unknown child of `2`, endpoint `3`	`[0, 1, 2, 3]`	`4`	none
`3` sees successful `4`, pop	`[0, 1, 2]`	`3`	`memo[3]: -1 → 1`
`2` sees successful `3`, pop	`[0, 1]`	`2`	`memo[2]: -1 → 1`
`1` sees successful `2`, pop	`[0]`	`1`	`memo[1]: -1 → 1`
`0` sees successful `1`, pop	`[]`	none	`memo[0]: -1 → 1`; return `true`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Each of n positions is solved once but can inspect up to n later landings, giving at most n(n - 1)/2 edges. The memo array has n entries; the explicit call stack contains at most n small frames. No input copy or path array is allocated. Frames replace native recursion, avoiding stack-limit failures at n = 10000. Java endpoints are at most 109999 before capping and fit int.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Arrays;3
4class Solution {5    public boolean canJump(int[] nums) {6        int n = nums.length;7        int[] memo = new int[n];8        Arrays.fill(memo, -1);9        memo[n - 1] = 1;10        // Each frame stores a position and its next child, simulating recursion.11        ArrayDeque<int[]> stack = new ArrayDeque<>();12        if (n > 1) stack.push(new int[] {0, 1});13        while (!stack.isEmpty()) {14            int[] frame = stack.peek();15            int pos = frame[0], next = frame[1];16            int end = Math.min(n - 1, pos + nums[pos]);17            if (next > end) {18                memo[pos] = 0;19                stack.pop();20            } else if (memo[next] == 1) {21                memo[pos] = 1;22                stack.pop();23            } else if (memo[next] == 0) {24                frame[1]++;25            } else {26                // Revisit this same child after its frame resolves.27                stack.push(new int[] {next, next + 1});28            }29        }30        return memo[0] == 1;31    }32}

Hints

Hint 1

Ask what single number summarizes everything the prefix of the array can do.

Hint 2

Decide what it means when the current index lies beyond that summary.

Hint 3

Update the summary with each index before testing whether the end is covered.

Edge Cases

Single element [0], which starts on the goal and returns true.
A zero that can be skipped, as in [2, 0, 0], which still returns true.
A zero wall before the end, as in [3, 2, 1, 0, 4], which returns false.

Common Mistakes and Interview Tips

Using a jump from an unreachable index; [0, 100000] must return false. Check the gap before extending the frontier.
Treating every zero as failure: [2, 0, 0] succeeds because an earlier jump bypasses it.
Assuming every jump must use the full value. The value is an upper bound, and shorter landings are legal.
Using native recursion on a long one-step chain can overflow Python, JavaScript or Java call stacks. Explicit frames retain the memoized search without that runtime limit.

Key Takeaway

When reachability only expands, maintain the frontier as one number and let each position extend it.