Jump Game

Check whether jumps can reach the last array position.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Jump Game: Scan only reachable positions and preserve the farthest index any processed jump can reach.

Input and goalCheck whether jumps can reach the last array position.

Initialize the reachable frontierBefore scanning, farthest=0, so only index 0 is known reachable.

index=0farthest=03021120344

examplenums = [3, 2, 1, 0, 4]reachableRange0..0farthest0

Recognize it

Each array value is a maximum forward jump and the question asks only whether the final position is reachable, not for a path or minimum jump count.

Keep true

Before index i is processed, every position through farthest is reachable using processed jumps; if i exceeds farthest, no earlier choice can reach i or anything beyond it.

Reuse it

When all feasible positions form a prefix, summarize every prior choice by its farthest boundary; this transfers to interval coverage, refueling reach, and minimum-jump layer scans.

Pattern: Greedy farthest reach.

Simple idea: Keep the farthest position reachable from everything processed. If the current position is past that point, it cannot be reached.

def can_jump(nums: list[int]) -> bool:
   farthest = 0

   for index, jump in enumerate(nums):
      if index > farthest:
         return False
      farthest = max(farthest, index + jump)
   return True

Cost: $O(n)$ time and $O(1)$ space.