Jump Game
Medium · rating 1400 · Greedy
The first line has n. The second line has n non-negative integers; ai is the maximum jump length from index i. Starting at index 0, print YES if you can reach the last index, otherwise NO.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Track the farthest index reachable so far. Scan left to right; if you ever stand on an index beyond that reach, you're stuck. Otherwise update the reach with i + a[i]. If the loop finishes, the last index was reachable.
Why greedy is optimal
Reachability is monotone: if index i is reachable then so is everything up to i + a[i], so the single farthest-reach value summarises all earlier jumps.
reach = 0
for i, x in enumerate(a):
if i > reach: return 'NO'
reach = max(reach, i + x)
return 'YES'Complexity
Time: O(n). Space: O(1).
Related problems
- Double-Booked? — Medium
- Fit the Most Tasks — Medium
- Matchmaking Gap — Medium
- Shopping on a Budget — Medium
- Partition Labels — Medium
- Cash Register Change — Medium