LeetCode 55 Jump Game - Example and Complexity Analysis

Trace nums = [3,2,1,0,4].

farthest = 0.

i=0: 0 <= 0. farthest = max(0, 0+3) = 3. i=1: 1 <= 3. farthest = max(3, 1+2) = 3. i=2: 2 <= 3. farthest = max(3, 2+1) = 3. i=3: 3 <= 3. farthest = max(3, 3+0) = 3. i=4: 4 > 3. Can't reach! Return false.

Trace nums = [2,3,1,1,4]. farthest evolves: 2 → 4 → 4 → 4 → 8. At i=4 (last), 4 <= 8. Reachable. Return true.

$O(n)$ time, $O(1)$ space.