greedy · Problem 2 of 2
Jump Game
You start at index 0. Each nums[i] is the maximum number of steps you
may jump forward from i. Return whether you can reach the last index.
canJump([2, 3, 1, 1, 4]) -> true
canJump([3, 2, 1, 0, 4]) -> falseThe tempting approach is to try every jump length from every position, which is exponential. The greedy insight makes it one pass: you never need to know which jumps you took, only how far you could possibly have got.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| canJump([2,3,1,1,4]) | a clear path to the end | true | — |
| canJump([3,2,1,0,4]) | a zero that traps you | false | — |
| canJump([0]) | a single element is already the end | true | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1)
One pass, one number. The greedy choice is safe because reachability is monotone — if you can reach index i you can reach everything before it, so the furthest reach is the only fact worth carrying.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left