Jump game
Each square says how far you may jump from it. Instead of trying routes, walk the squares once and keep one number: the furthest square you could reach so far. If you ever stand on a square beyond that, you are stuck; if it covers the end, you are done.
23114
Each number is the longest jump from that square. Starting on the first square, can you reach the last?
1function canReachEnd(jumps) {2 let furthest = 0;3 for (let i = 0; i < jumps.length; i++) {4 if (i > furthest) return false;5 furthest = Math.max(furthest, i + jumps[i]);6 }7 return true;8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the first jump is 0 and there is more than one square |
| average | n | one pass over the squares |
| worst | n | trying every route instead can take exponential time |
| space | 1 | just the furthest reachable square |
Where it breaks
- Trying every route. Following each possible jump from each square branches out fast. The greedy scan never needs to know which route works, only how far some route can get.
- Zeros are the traps. Pick A trap: every route lands on the 0 at square 3 and stops there. The furthest reachable square stays at 3, so square 4 is out of reach.
- Why greedy is safe here. If square k is reachable, so is every square before it. That is what makes one number enough. Ask instead for the fewest jumps and you need a slightly smarter scan.