55. Jump Game — DSA Atlas

MediumGreedy AlgorithmsGreedy reachability sweepGreedy farthest-reach

Jump Game

Given a 0-indexed array nums where each nums[i] is the maximum jump length from index i, determine whether you can reach the last index starting from index 0. Return true if reachable, otherwise false.

Open official problem prompt ↗

In plain English

Decide whether a chain of forward jumps can carry you from the first cell all the way to the last.

Picture it like this

Like refueling a car where each cell's value is how much gas it grants: as long as you never coast to a stop before the next station, you keep pushing your maximum range forward until it covers the finish line.

Example

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

Constraints

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

Pattern lesson

See the pattern, then code

Greedy farthest-reach

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. You can reach the end iff, as you scan left to right, no index ever sits beyond the farthest position you have proven reachable so far; each reachable cell can only extend that frontier.

New words, made simpleKnow these before the algorithm

farthest / frontier: The rightmost index you have proven you can still reach.
dead index: An index that lies beyond the frontier and can never be stepped on.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Backtracking / recursion

Exponential blowup on adversarial inputs.

Try every jump length from each cell recursively.

Time O(2^n)Space O(n)

DP over reachability

Correct but quadratic and needs extra memory.

dp[i] true if some earlier reachable j can jump to i.

Time O(n^2)Space O(n)

Best choiceGreedy frontier scan

Single linear pass, constant space.

Track the farthest reachable index and fail the moment an index escapes it.

Time O(n)Space O(1)

The rule we keep true

Invariant

Before examining index i, farthest holds the maximum index reachable using only indices 0..i-1; if i <= farthest then i is reachable.

Why this is correct

Reasoning

Reachable indices form a contiguous prefix: if index i is reachable then so is every index before it, and any reachable cell can only push the frontier rightward. The only way to fail is a hard gap where an index exceeds the current frontier, which the scan detects immediately.

The algorithm in three movesSay these aloud before coding

1Track the farthest reachable index, starting at 0

i=0 reach=2

2Scan each index i; if i exceeds farthest, the frontier has a gap so return false

i=1 reach=max(2,4)=4

3Otherwise update farthest = max(farthest, i + nums[i])

i>=2 all <= reach -> true

4If the loop finishes (or farthest covers the last index) return true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read-

2 · AskStarting frontier?

3 · Update statefarthest=0

4 · ResultBegin scan.

Key takeaway

The reachable frontier grows to cover the last index, so every cell stays within reach.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2Frontier init
farthest starts at 0, the only index guaranteed reachable at the start.
2
Lines 3-5Gap check
If the current index sits beyond the frontier, no earlier cell could jump here, so the end is unreachable.
3
Lines 6Extend frontier
Each reachable cell may push the farthest reachable index further right.
4
Lines 7Success
Completing the scan without a gap means the last index was always within reach.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element array trivially returns true
A leading 0 with length 1 returns true, but a 0 that blocks progress before the end returns false
Large jump values that overshoot the array still count as reaching the end

Common beginner mistakes

Returning early with true only when farthest >= last index but forgetting the gap check for false cases
Updating farthest before checking whether the current index is even reachable
Treating a 0 anywhere as automatic failure, even when it is at or past the last index

Check your understanding

How does the algorithm detect that index i is unreachable?

Jump Game

Jump Game

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms