AlgoMaster Logo

Jump Game

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We start at index 0, and at each index i, we can jump forward by up to nums[i] positions. The question is whether some sequence of jumps lands us at or beyond the last index.

We are not looking for the shortest path or the minimum number of jumps. We only need a yes or no answer, which means we never have to enumerate individual paths.

The only thing that can block us is a zero, or a run of values too small to carry us past a later zero. If the array contains no zeroes, every index is reachable and the answer is always true. The work is deciding whether the path can clear any zeroes that appear before the last index.

Key Constraints:

  • 1 <= nums.length <= 10^4 → With n up to 10,000, an O(n^2) solution runs about 100 million operations in the worst case, which is on the edge of acceptable. An O(n) pass is well within limits.
  • 0 <= nums[i] <= 10^5 → Values are non-negative, so a jump never moves backward. Reachability only flows forward, and a value of 0 is the only entry that can stop forward progress.

Approach 1: Dynamic Programming (Bottom-Up)

Intuition

Define reachability directly: index i is reachable when some earlier reachable index j can jump to it, meaning j + nums[j] >= i. The answer is whether the last index is reachable.

Build a boolean array dp where dp[i] means index i is reachable from index 0. Set dp[0] = true because we start there. For every other index i, scan earlier indices j. If j is reachable (dp[j]) and can jump to i (j + nums[j] >= i), then dp[i] = true.

This computes the right answer but is slow: each index scans the indices before it.

Algorithm

  1. Create a boolean array dp of size n, initialized to false.
  2. Set dp[0] = true since we start at index 0.
  3. For each index i from 1 to n - 1:
    • For each index j from 0 to i - 1:
      • If dp[j] is true and j + nums[j] >= i, set dp[i] = true and break.
  4. Return dp[n - 1].

Visualization and Code

Loading animation...

Storing reachability for every index is more information than the problem needs. The next approach replaces the whole array with a single number: the farthest index reachable so far.

Approach 2: Greedy (Forward Pass - Max Reach)

Intuition

Instead of asking "is index i reachable?" for every index, track one value: the farthest index reachable so far, maxReach.

Walk through the array left to right. At index i, if i <= maxReach then i is reachable, and from i we can jump as far as i + nums[i], so update maxReach = max(maxReach, i + nums[i]).

If i > maxReach at any point, index i is unreachable and no later index can help, so return false. If maxReach >= n - 1 at any point, the last index is reachable.

Algorithm

  1. Initialize maxReach = 0 (we start at index 0, so that's the farthest we know we can reach).
  2. Iterate through the array with index i from 0 to n - 1:
    • If i > maxReach, return false (we can't reach this index).
    • Update maxReach = max(maxReach, i + nums[i]).
    • If maxReach >= n - 1, return true (we can reach the end).
  3. Return true (the loop completed, meaning we reached the last index).

Visualization and Code

Loading animation...

The next approach is also O(n) but reverses the direction. Instead of expanding reach forward from the start, it shrinks a goal backward from the last index.

Approach 3: Greedy (Backward Pass - Goal Post)

Intuition

Instead of tracking how far forward we can reach, reverse the problem. Place the goal at the last index, then scan backward. For each index, check whether it can reach the current goal, and if it can, move the goal to that index.

If index j can jump to the goal (j + nums[j] >= goal), then reaching j is enough to reach the end. The problem reduces to "can we reach index j?", and we repeat, moving the goal leftward each time it succeeds.

If the goal reaches index 0, the last index is reachable from the start.

Algorithm

  1. Set goal = n - 1 (the last index).
  2. Iterate backwards from i = n - 2 down to 0:
    • If i + nums[i] >= goal, set goal = i (we can reach the old goal from here).
  3. Return true if goal == 0, false otherwise.

Visualization and Code

Loading animation...