Picture nums as a row of stepping stones. You start on the first stone, index 0. From the stone at index i you may jump forward to any stone from i + 1 up to i + nums[i], so nums[i] is the longest jump allowed from there. A stone holding 0 doesn't let you move at all.
Return true if some sequence of jumps lands you on the last stone, and false otherwise.
From index 0 the only jump is to index 1. From there, jumping 2 reaches index 3, which skips the 0. One more jump of 1 lands on the last stone.
Every route ends on index 2: index 0 jumps there or to index 1, and index 1 only reaches index 2. Its 0 lets you go no further, so the last stone is out of reach.
There is only one stone, so you are already on the last one.
Constraints
1 <= nums.length <= 10⁴0 <= nums[i] <= 10⁵You don't need the route, only how far you can get. If you can stand on index i, you can stand on every index before it too, so the reachable stones always form one unbroken run from the start.
The obvious plan is to try routes: from each stone, try every jump length, and see if any route ends on the last stone. The routes multiply at every stone, so this explodes: with long jumps everywhere and the last stone just out of reach, a search has to rule out an exponential number of routes before it can say false.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
true