Can you reach the end?
Decide whether you can hop from the first cell to the last when each cell says how far you may jump, by tracking the farthest cell reachable so far. About 15 minutes.
One number: how far
Each cell holds the longest jump you may take from it. A jump of 3 lets you land on any of the next 3 cells, or fewer. You start on the first cell and want to land on the last.
Instead of exploring every path, keep one number: the farthest cell you could reach so far. Every cell up to that number is reachable, because you can always take a shorter jump.
Scan and update
Scan from the left. At each cell, first check that it is within the reach. If it is beyond, no jump ever lands here, and you are stuck.
Otherwise, update the reach to the larger of the old reach and this cell's position plus its jump. If the reach ever covers the last cell, the answer is yes. A single pass is enough, with no backtracking.
far = 0 far = max(far, i + jump)
Cell 0 allows 3 steps. The farthest reach is 3.
Jumps 2, 3, 1, 1, 4. Can you reach the last cell?
- AYes
- BNo
- COnly if you take the longest jumps
Show the answer
Yes. From cell 1 the 3 reaches cell 4, and cell 1 is reachable from cell 0.
Reach the last cell
You stand on the first cell of an array nums. nums[i] is the longest jump you can take from cell i, and you may jump any shorter distance forward too. Return true if you can reach the last cell.
nums = [2, 3, 1, 1, 4] → true
1 ≤ nums.length ≤ 100,000 · 0 ≤ nums[i] ≤ 100,000