Jump Game

Each element is your maximum jump length from that position. Starting at index 0, decide whether you can reach the last index.

A way to picture it

Every tile is a trampoline with a maximum bounce. Walk forward keeping track of the farthest tile any trampoline so far could launch you to. If you ever stand on a tile beyond that frontier, you could never have got there.

How to approach it

Track reach = max(reach, i + nums[i]). If i ever exceeds reach, you're stuck; if reach covers the last index, you win.

Example

Input: {"nums":[2,3,1,1,4]}. Output: true.

Complexity: O(n) time and O(1) space. One pass, one variable.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.