Jump Game

You are given an array nums where nums[i] is the maximum jump length from index i. Starting at index 0, return true if you can reach the last index.

A naive search tries all paths. A greedy scan works by tracking the farthest reachable index so far.

Why this is worth learning

You do not need to choose a path. You need a certificate that every scanned index lies within a prefix known to be reachable.

Before coding: one-minute experiment

Why must [1,0,100] return false even though its last entry is large?

Function signature

func CanJump(nums []int) bool

Inputs / outputs

• nums: non-empty slice of non-negative integers.
• Return: true if the last index is reachable, else false.

Example

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

Reason: from 0 you can reach 1, then jump to the end.

Constraints

• 1 <= len(nums) <= 100_000
• 0 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Track the farthest index you can reach while scanning left to right.

Invariant: before processing index i, all indices <= farthest are reachable.

If you ever see i > farthest, you are stuck and must return false.

Algorithm (step-by-step)

1. Set farthest = 0.
2. For each index i from 0 to len(nums)-1:
   • If i > farthest, return false.
   • Update farthest = max(farthest, i + nums[i]).
3. If the loop ends, return true.

Correctness sketch

After reachable positions before i have been processed, farthest is the maximum endpoint available from those positions; all indices from zero through farthest are reachable because a jump may use any smaller length. If i exceeds farthest, no previously reachable position can cross the gap, so reaching the end is impossible. Otherwise i is reachable and its jump can safely extend farthest. The scan never uses a jump from an unreachable index. If no gap is found before the last index, that index is reachable.

Trace (hand walkthrough)

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

Reason: from 0 you can reach 1, then jump to the end.

Walk:
- i=0: farthest=max(0,0+2)=2
- i=1: farthest=max(2,1+3)=4
- i=2: farthest=4; i=3: farthest=4
- i=4 is reachable; processing its jump makes farthest=max(4,4+4)=8
- return true; endpoints beyond the array do not need to be visited

Pitfalls to avoid

• Using a jump from an unreachable index. After extending from a reachable index, returning early when farthest >= len(nums)-1 is safe.
• Forgetting the stuck check i > farthest.

Debugging lens

Place a very large jump immediately after a zero trap. A solution that updates farthest before checking i>farthest will incorrectly use unreachable information.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Under these bounds, i + nums[i] <= 1_000_099_999, which fits even a signed 32-bit integer. The reach may exceed the last index; it is a bound, not an index to read.

Reconstruction checkpoint

Why must [1,0,100] return false even though its last entry is large?

Return to Array & String · Module quiz