Jump Game

Problem

Autonomous delivery drones follow a route where each waypoint records the maximum distance the drone can travel forward from that position. Given the route as an integer array where each element is the max jump length from that position, determine whether the drone can reach the final waypoint starting from the first.

Input: [2, 3, 1, 1, 4]  -> True   (0->1->4 or 0->2->3->4)
Input: [3, 2, 1, 0, 4]  -> False  (stuck at index 3, can't pass)
Input: [0]              -> True   (already at the last index)

Solution

Approach: greedy reachability frontier - one running maximum.

Carry a single number, farthest, the highest index reachable from anything seen so far. Walk left to right. At each index, first check if index > farthest: return False - if the frontier never stretched far enough to cover this position, there is a gap nothing could clear, so the last index is unreachable. Only after passing that check do you extend the frontier with farthest = max(farthest, index + nums[index]), because index + nums[index] is the farthest you can leap from here. If the loop finishes without ever falling behind the frontier, every index was reachable, so return True.

The order of the two operations is the whole trick. Checking reachability before extending means you never grow the frontier from a position you could not actually stand on - doing it the other way would paper over a true gap. Greedy is valid here because a wider reach never hurts: there is no trade-off between positions, so always maximizing reach is also the global optimum. Trace [3,2,1,0,4]: farthest goes 3,3,3,3 through indices 0-3, but index 4 > 3, so it returns False - the zero at index 3 traps the frontier. For [2,3,1,1,4], index 1 lifts farthest to 4 and the frontier already covers the end.

Edge cases: a single-element array returns True with the loop never failing the check; a 0 that the frontier exactly reaches but cannot pass (e.g. [1,0,0]) correctly returns False.

Complexity: O(n) time, O(1) space - one pass holding a single integer.