Jump Game

You are given an integer array nums. You start at the first index, and each nums[i] is the maximum length of a forward jump from index i.

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

Hints

· Stuck? Reveal one nudge at a time.

You don't need the exact path — just how far you can possibly reach.

Sweep left to right, keeping the farthest index reachable so far.

If an index lies beyond that farthest reach, you can never arrive — return false.

Common doubts

If the farthest reachable index covers position i, then i is reachable; the specific route doesn't matter, only whether the frontier extends to the end.

It's the only failure condition: if the current index is past everything you could reach, no earlier jump lands here, so the end is unreachable.

No — a zero only traps you if the frontier doesn't already extend beyond it. If an earlier jump reaches past the zero, it's harmless.

Interview follow-ups

· What an interviewer asks next.

Extend the greedy: track the current jump's frontier and the next reachable frontier, incrementing a jump count when you exhaust the current one.

Remember, for each frontier extension, which index produced it; then walk those choices back from the end.

Fun facts

This 'farthest reachable' frontier is a one-dimensional version of a BFS wavefront — you're implicitly doing breadth-first reachability in O(1) space.
The same running-maximum-of-reach idea underlies interval covering and gas-station problems.

Asked at

AmazonGoogleMicrosoftMeta

Frequently Sometimes Occasionally

Example 1

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

Example 2

Input: nums = [3,2,1,0,4]
Output: false
You always arrive at index 3 (value 0), which you can't move past to reach the end.

Constraints

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

You don't need to plan a specific path — you only need to know how far you can possibly get. Track the farthest index reachable so far, and the moment an index sits beyond that frontier, you're stuck.

Prerequisites

Before you start

· Concepts used directly in the solution.

Reachability. An index is reachable if some earlier index can jump to it or past it.

Running maximum. Keeping the best value seen so far in a single sweep.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Is each jump exactly nums[i], or up to nums[i]?”

Up to — from index i you may land anywhere in i+1 .. i+nums[i].

“What does a 0 mean?”

You can't move forward from that index; you're stuck there unless something jumped past it.

Edges

“What if the array has length 1?”

You're already on the last index, so the answer is true.

The ideal opening — say it like this

I'll track the farthest index I can reach as I sweep left to right.

At each index, if it's already beyond my farthest reach, I can never get here, so I fail.

Otherwise I extend the frontier with i + nums[i]. If the frontier ever covers the last index, I'm done.

Understand the problem

Worked example — nums = [2, 3, 1, 1, 4]

i=0  farthest=0, in reach; extend to 0+2=2
i=1  farthest=2, in reach; extend to 1+3=4  -> covers last index
i=2  farthest=4, in reach; extend to 2+1=3 (no change)
...  frontier already >= 4 (last) -> true

Key observations

1Aha

Only the frontier matters

You never need the exact path — just whether the last index falls within the farthest reach you can accumulate. One integer captures everything.

2Aha

An index past the frontier is fatal

If i is greater than the current farthest reach, no earlier index could jump to i, so the last index is unreachable — return false immediately.

3Aha

Extend greedily, never shrink

At each reachable i, update farthest = max(farthest, i + nums[i]). The frontier only grows, so a single left-to-right pass settles it.

Brute force vs optimal

	Reachability DP	Farthest-reach greedy
Idea	Mark each index good if it can reach a good index	Track the farthest index reachable so far
Time	O(n^2)	O(n)
Space	O(n)	O(1)

The DP recomputes reachability per index; the greedy collapses it into one running frontier. Full code is in the Approaches selector below.

Summary

Key takeaway

Sweep once, tracking the farthest index reachable. If any index lies beyond that frontier you're stuck; otherwise extend it with i + nums[i]. Reaching (or passing) the last index means success — O(n) time, O(1) space.

farthest = 0
for i in 0 .. n-1:
    if i > farthest: return false      # unreachable
    farthest = max(farthest, i + nums[i])
return true