Can you get to the end

You start at position 0. Each value says the most you may jump forward from that position; you may jump anything from zero up to it. Say whether the last position can be reached.

Worked example#

[2, 3, 1, 1, 4] is true. Jump 1 to position 1, then 3 to position 4.

[3, 2, 1, 0, 4] is false. Whatever you do you land on position 3, which allows a jump of 0, and nothing can get past it.

The idea#

The tempting approach is to try every jump from every position, which is exponential, or to fill a table of "can I reach the end from here", which is n².

Neither is needed, and seeing why is the point of this problem.

Walk left to right keeping one number: the furthest position reachable so far.

At each position, first check whether you have already fallen behind. If the current position is beyond the furthest reachable, nothing can get here and the answer is false. Otherwise, this position is reachable, so update the furthest to max(furthest, here + jump).

reach = 0
for each position i with jump nums[i]:
    if i > reach: return false        # nothing can get here
    reach = max(reach, i + nums[i])
return true

Why one number is enough#

Because reachability has no gaps. If position 7 is reachable then so is every position before it, since any jump can be shortened. So "the set of reachable positions" is always a prefix, and a prefix is fully described by where it ends: one number.

That is the whole reason greedy works here, and it is the kind of thing worth checking before trusting a greedy solution. When the reachable set is not a simple prefix, this argument collapses and so does the algorithm.

Why you never need to choose a jump#

Nothing is ever decided. You are not picking a route, only tracking how far routes could possibly go. There is no choice to get wrong, which is why there is no backtracking and no table.

Constraints#

• 1 <= n <= 100000
• 0 <= nums[i] <= 100000