Jump Game

Problem

You are standing on the first cell of an integer array nums. The value in each cell is the maximum number of cells you may move forward from it in a single jump (you may jump fewer). Return True if it is possible to reach the last cell, and False otherwise.

• nums has between 1 and 50,000 cells.
• Each value is a non-negative integer no larger than 1,000,000 (jumps past the end are allowed and simply land on the last cell).
• A single-cell array counts as already at the end.

Examples

• nums = [3, 1, 2, 0, 1, 5] → True. Jump 2 to index 2, then 2 to index 4, then 1 to the end; jumping the full 3 from the start lands on the zero at index 3.
• nums = [2, 1, 0, 3, 2] → False. From index 0 you can reach only indices 1 and 2, and both of them lead to the zero at index 2.
• nums = [4] → True. You start on the last cell.

Hints

1. A zero is only a problem if you cannot jump over it. What is the farthest cell you can reach so far?
2. As you scan left to right, when does a cell become unreachable?
3. Track the maximum reachable index; if the scan ever reaches a cell beyond it, return False.