Jump Game
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Each number is the maximum jump length from that position. Starting at the first position, can you reach the last?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you can reach a position, can you reach everything before it?
- Hint 2Keep the largest position + jump you have seen so far.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Crossing a river on stepping stones where each stone says how far you may leap from it. You keep one number in your head: the farthest stone you could possibly reach so far. Walk the stones one by one; if you ever stand on a stone beyond your farthest reach, you were never able to get there, so you are stuck. If your farthest reach covers the last stone, you can cross.
- The obvious way
Try all jump choices recursively: O(2^n).
- The key insight
Keep farthest = 0. Visit each position: if the position is beyond farthest, return False. Otherwise farthest = max(farthest, position + jump here). If you finish the loop, True.
- The algorithm
- farthest = 0.
- Visit positions left to right.
- Position beyond farthest? Stuck: False.
- Else farthest = max(farthest, position + jump).
Watch it run
Examplenums = [2, 3, 1, 1, 4]
Stone 0 lets you leap 2: you can reach up to stone 2.
farthest = 2
Where people slip
- A 0 is only a problem if you cannot jump past it from an earlier stone: the farthest tracking handles this.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def can_jump(nums):
farthest = 0 # the farthest stone we could possibly reach
for position, leap in enumerate(nums):
if position > farthest:
return False # we could never have stood here
farthest = max(farthest, position + leap)
return TrueNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.