Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Jump Game

LeetCode #55Medium
Track the farthest index you can reach

Given an array where each element is the maximum jump length from that position, determine whether you can reach the last index starting from the first index.

Asked atAmazonGoogleMicrosoft
step 1 / 8
2
3
1
1
4
[0][1][2][3][4]
Greedy · farthest reach in one pass
▸
1given nums
2farthest ← 0
3for i ← 0 to n − 1:
4    if i > farthest: return false
5    farthest = max(farthest, i + nums[i])
6    if farthest ≥ n − 1: return true
7return true
state
  • n5
  • last4
  • nums[2, 3, 1, 1, 4]

line 1Jump Game: from index i you may jump up to nums[i] steps forward. Can we reach the last index? The greedy idea is to track ONE number — farthest, the maximum index reachable so far — and never look back.