Can you reach the last position?
You start at position 0 of a list nums. From position i you may jump forward by any
distance from 1 to nums[i]. Return true if you can reach the last position.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2,3,1,1,4] | true | 0 → 1 → 4. |
nums = [3,2,1,0,4] | false | Every route lands on position 3, whose jump is 0. |
nums = [0] | true | Already at the last position. |
Constraints
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁵
Hints
Hint 1
good[i] = can the end be reached from i. good[n − 1] = true.
Hint 2
good[i] = some j in i + 1 .. i + nums[i] has good[j].
Hint 3
Better: going right to left, track the leftmost good position; i is good if i + nums[i] reaches it.
Where people lose marks
- Jumping exactly nums[i] instead of up to nums[i].
- An O(n²) DP that times out on long lists with large jumps.
Dry run on [3,2,1,0,4]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5nums3021120344good·0·1·2·3T4
The last position is good. leftmost = 4.
-
Step 2 / 5nums3021120344good·0·1·2F3T4
3 + 0 = 3 < 4: position 3 is not good.
-
Step 3 / 5nums3021120344good·0·1F2F3T4
2 + 1 = 3 < 4: position 2 is not good.
-
Step 4 / 5nums3021120344good·0F1F2F3T4
1 + 2 = 3 < 4: position 1 is not good.
-
Step 5 / 5nums3021120344goodF0F1F2F3T4
0 + 3 = 3 < 4: position 0 is not good. Position 0 is not good: the end cannot be reached.
How to think about it
As a DP from the right: position i can reach the end if one of the positions it can jump to can. That is
O(n · max jump). The table has a special structure, though: if a position is good, it suffices to know the
leftmost good position to its right, because any jump that reaches past it can stop there. So scan right to left
keeping leftmost; position i is good when i + nums[i] ≥ leftmost, and then becomes the new
leftmost. The answer is whether position 0 ends up good.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def can_reach_end(nums):
leftmost = len(nums) - 1 # leftmost position known to reach the end
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= leftmost:
leftmost = i
return leftmost == 0#include <vector>
bool solve(const std::vector<int>& nums) {
int leftmost = nums.size() - 1;
for (int i = (int)nums.size() - 2; i >= 0; --i)
if (i + nums[i] >= leftmost) leftmost = i;
return leftmost == 0;
}class Solution {
public boolean canReachEnd(int[] nums) {
int leftmost = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) if (i + nums[i] >= leftmost) leftmost = i;
return leftmost == 0;
}
}function canReachEnd(nums) {
let leftmost = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) if (i + nums[i] >= leftmost) leftmost = i;
return leftmost === 0;
}fn solve(nums: &[i64]) -> bool {
let mut leftmost = nums.len() as i64 - 1;
for i in (0..nums.len().saturating_sub(1)).rev() {
if i as i64 + nums[i] >= leftmost {
leftmost = i as i64;
}
}
leftmost == 0
}solve :: [Int] -> Bool
solve nums = foldr step (length nums - 1) (zip [0 ..] (init nums)) == 0
where step (i, x) leftmost = if i + x >= leftmost then i else leftmost
Variants to try
- The fewest jumps to reach the end (breadth-first levels, or greedy).
- Jumps may go left or right: breadth-first search.
- Each position has a cost: Dijkstra or a DP with a deque.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minLargest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Medium20 minWays to decode a string of digits
Letters are encoded as 1 to 26. Count the ways to read a string of digits back as letters: one digit or two at a time, with zeros as the trap.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minLargest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Medium20 minWays to decode a string of digits
Letters are encoded as 1 to 26. Count the ways to read a string of digits back as letters: one digit or two at a time, with zeros as the trap.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.