Reachability (jump game)
In one line
Track the farthest index you can reach so far; if you ever stand beyond it you are stuck, and counting how often you must extend that frontier gives the minimum number of jumps.
What it is
In Jump Game I you get an array where nums[i] is the maximum jump length from index i, start at index 0, and must say whether you can reach the last index. In Jump Game II the end is guaranteed reachable and you must find the fewest jumps.
Both have a natural DP or BFS solution in O(n^2), but a greedy single pass does it in O(n). The key state is reach, the farthest index reachable using the indices seen so far. Every index up to reach is reachable, because you can always jump shorter than the maximum.
For the minimum number of jumps, think of BFS levels: all indices reachable with k jumps form one contiguous range. The next range ends at the farthest point reachable from anywhere in the current range.
Why interviewers ask
It tests whether you can see that a DP with O(n^2) transitions collapses into one number (the frontier). Interviewers often accept the DP first and then ask you to optimise; explaining the BFS-level view of Jump Game II shows you understand why the greedy is correct, not just the code.
How it works
- 1Jump Game I: set reach = 0. For each index i from left to right: if i > reach, index i cannot be reached, return false. Otherwise update reach = max(reach, i + nums[i]).
- 2If the loop finishes (or reach is at least the last index), return true. You can stop early once reach >= n - 1.
- 3Jump Game II: keep jumps = 0, cur_end = 0 (the last index reachable with the current number of jumps) and farthest = 0.
- 4For i from 0 to n - 2: farthest = max(farthest, i + nums[i]). When i == cur_end you have exhausted the current level, so jumps += 1 and cur_end = farthest.
- 5Stopping at n - 2 avoids counting an extra jump when you are already standing on the last index. Both versions are O(n) time and O(1) space.
Worked example · Tracing [2, 3, 1, 1, 4] and [3, 2, 1, 0, 4]
- Jump Game I on [2,3,1,1,4]: i=0, reach = max(0, 0+2) = 2. i=1, reach = max(2, 1+3) = 4, which is already the last index. Answer true.
- Jump Game I on [3,2,1,0,4]: i=0 reach 3; i=1 reach max(3,3) = 3; i=2 reach 3; i=3 reach max(3, 3+0) = 3. i=4: 4 > 3, return false. Every path lands on the 0 at index 3.
- Jump Game II on [2,3,1,1,4]: start jumps 0, cur_end 0, farthest 0.
- i=0: farthest = 2. i == cur_end, so jumps = 1, cur_end = 2 (level 1 is indices 1 to 2).
- i=1: farthest = max(2, 4) = 4. i=2: farthest = max(4, 3) = 4. i == cur_end, so jumps = 2, cur_end = 4.
- i=3: farthest stays 4; loop ends at n-2 = 3. Answer 2 jumps: 0 to 1, then 1 to 4.
Picture it
Imagine crossing a river on stepping stones where each stone tells you how far you can leap from it. You do not need to plan the exact route; you only need to keep track of the farthest stone you could land on so far. If you ever reach a stone beyond that line, you have fallen in.
Reference code
def can_jump(nums):
"""Jump Game I: can we reach the last index?"""
reach = 0
for i, step in enumerate(nums):
if i > reach: # this index is unreachable
return False
reach = max(reach, i + step)
return True
def min_jumps(nums):
"""Jump Game II: fewest jumps to the last index (assumed reachable)."""
jumps = 0
cur_end = 0 # end of the range reachable with `jumps`
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end: # must jump again to go further
jumps += 1
cur_end = farthest
return jumps
# can_jump([2,3,1,1,4]) -> True, can_jump([3,2,1,0,4]) -> False
# min_jumps([2,3,1,1,4]) -> 2
can_jump keeps the farthest reachable index and fails as soon as an index lies beyond it. min_jumps treats each [previous end + 1, cur_end] range as one BFS level. Both are O(n) time and O(1) space.
Key patterns
Reachability frontier
When: Can you get from the start to the end with variable step limits?
How: Keep reach = max(i + nums[i]); fail if i > reach.
Minimum jumps as BFS levels
When: Fewest steps where each position reaches a contiguous range
How: Track cur_end and farthest; when i hits cur_end, count a jump and set cur_end = farthest.
Interval covering
When: Fewest intervals to cover [0, T] (video stitching, minimum taps)
How: Convert to 'farthest reach from each start' and run the Jump Game II greedy; return -1 if farthest does not move past cur_end.
When greedy fails: jump game with costs or exact moves
When: Jumps have costs or must be exact (Jump Game III, frog jump)
How: Use BFS/DFS over states or DP; the frontier trick only works when every shorter jump is allowed.
Real-world use
Covering a timeline with clips
Video editors and the 'video stitching' problem choose the fewest clips that cover a timeline; the same frontier-extension greedy picks, at each point, the clip that reaches farthest.
Irrigation and sensor coverage
Placing the fewest sprinklers, taps or sensors whose ranges cover a whole line (for example along a road or pipeline) reduces to minimum jumps over the coverage intervals.
Network hop counts
When every node can forward to any node within a range, the minimum hop count is the BFS level computation that Jump Game II performs in one pass, as in relay planning for linear radio chains.
Game level validation
Platformer level tools check that every level is completable by computing which platforms are reachable from the start with the player's jump distance, the same reachability frontier idea.
In a project
A delivery drone service along a 40 km coastline has charging pads at known kilometre marks, each allowing a different flight range depending on its battery type. Operations wants to know if a drone can reach the far end and with the fewest recharges.
- Model pads as positions with a range, sorted by position; the start point is the depot.
- Run the reachability sweep: keep the farthest point reachable so far, and fail fast if the next pad lies beyond it.
- Run the level-based greedy to count recharges: each time you pass the end of the current range, count a recharge and extend to the farthest point seen.
- Return the recharge count and the gaps that make some routes impossible so the team knows where a new pad is needed.
Impact: Route checks run in O(n) per route instead of a quadratic DP, so planners can test thousands of pad layouts per second, and the report points directly at the stretch of coast that needs a new pad.
Trade-offs
Use it when
- From each position you may jump any distance up to a limit
- You need yes/no reachability or the minimum number of jumps
- Covering a line with the fewest intervals
Avoid it when
- Jumps must be an exact length or can go backwards (use BFS/DFS)
- Each landing has a cost to minimise (use DP or Dijkstra)
- You need to count the number of ways (use DP)
Cost: O(n) time and O(1) space for both versions, versus O(n^2) for the straightforward DP.
Common mistakes
- Writing an O(n^2) DP or recursion without memoization that times out on 10^4 elements.
- In Jump Game II, looping to n - 1 instead of n - 2 and counting one jump too many.
- Greedily jumping to the index with the largest value instead of the one that reaches farthest (i + nums[i]).
- Forgetting the zero trap: a 0 inside the array is only a problem if reach cannot pass it.
- Not handling a single-element array (already at the end: true, 0 jumps).
Interview questions
Quick revision
- Jump I: reach = max(reach, i + nums[i]); i > reach means false.
- Reachable set is always a prefix [0, reach].
- Jump II: farthest, cur_end; at i == cur_end, jumps++ and cur_end = farthest.
- Loop to n - 2 in Jump II.
- Choose by farthest landing reach, not the biggest number.
- O(n) time, O(1) space; the DP is O(n^2).
- Exact or backward jumps need BFS, not this greedy.
Check yourself
1. For nums = [3, 2, 1, 0, 4], can you reach the last index?
2. What is the minimum number of jumps for [2, 3, 1, 1, 4]?
3. Why does Jump Game II's loop stop at index n - 2?
4. What is the time complexity of the greedy solutions?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.