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.

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

• Invariant: before processing index i, all indices <= farthest are reachable.
• The algorithm maintains a feasible best-so-far state while scanning.
• Each greedy update preserves feasibility and never discards a possible optimal answer.
• When the scan ends, the recorded state represents the optimal solution.

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: farthest=4 -> reachable

Pitfalls to avoid

• Returning early just because farthest reaches the end (still ok, but ensure no bounds issues).
• Forgetting the stuck check i > farthest.

Complexity

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

Implementation notes (Go)

• Use 64-bit if you worry about overflow of i + nums[i].