#55 Jump Game
frequently reported atAdobeAmazonBloombergMicrosoftGoogleMeta
the problem
In plain words
You start at index 0. nums[i] is the longest jump allowed from index i (any shorter jump is fine too). Return true if you can land on the last index.
in nums = [2,3,1,1,4]
out true
Jump 1 step to index 1, then 3 steps to the end.
in nums = [3,2,1,0,4]
out false
Every path lands on index 3, whose jump length is 0.
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 10⁵
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy furthest reach
You don't need to know how you got somewhere. Track only the furthest reachable index. Every index before it is reachable too.
solutions
From brute force to optimal
From each index, recursively try every jump length.
- If i ≥ n − 1, return true.
- For step = 1..nums[i], recurse on i + step.
- If none succeeds, return false.
The same index is re-solved along many paths. With big jumps, the number of paths doubles per index.
The recursion depth can reach n.
class Solution { public boolean canJump(int[] nums) { return from(nums, 0); } private boolean from(int[] nums, int i) { if (i >= nums.length - 1) return true; // reached (or passed) the last index for (int step = 1; step <= nums[i]; step++) { if (from(nums, i + step)) return true; // try every jump length } return false; }}good[i] is true if some index within nums[i] steps of i is good. The last index is good.
- good[n−1] = true.
- For i from n−2 down to 0, scan j in (i, i + nums[i]] for a good index.
- Return good[0].
Each index may scan up to n later indices.
The boolean table.
class Solution { public boolean canJump(int[] nums) { int n = nums.length; boolean[] good = new boolean[n]; // good[i]: from i you can finish good[n - 1] = true; for (int i = n - 2; i >= 0; i--) { int furthest = Math.min(n - 1, i + nums[i]); for (int j = i + 1; j <= furthest; j++) { if (good[j]) { good[i] = true; break; } } } return good[0]; }}Walk left to right and keep reach, the furthest index reachable so far. If i ever exceeds it, you're stuck.
- reach = 0.
- For each i: if i > reach, return false.
- reach = max(reach, i + nums[i]); if reach ≥ n − 1, return true.
One pass with O(1) work per index.
One integer.
class Solution { public boolean canJump(int[] nums) { int reach = 0; // furthest index reachable so far for (int i = 0; i < nums.length; i++) { if (i > reach) return false; // can't even stand on i reach = Math.max(reach, i + nums[i]); if (reach >= nums.length - 1) return true; } return true; }}Dry run
in the room
How to say it in the interview
talk track
- Start with "recursion tries every jump, so it's exponential. A DP over indices gives O(n²)."
- Then: "The reachable indices always form a prefix [0..reach], so one integer is enough."
- Walk through [3,2,1,0,4] to show
i > reachtriggering at index 4.
traps
- Returning false as soon as nums[i] == 0. A zero is only a problem if nothing reaches past it.
- Forgetting that n = 1 is already true.
what they ask next
Follow-ups
Another O(n) way?
Walk backwards with a goal: if i + nums[i] ≥ goal, set goal = i. The answer is goal == 0.
Fewest jumps?
That's LC 45 Jump Game II. Same scan, but count BFS levels.
before you submit
Edge cases to test
- [0] → true: you already stand on the last index.
- [0, 1] → false: stuck on the first index.
- [2, 0, 0] → true: zeros you can jump over don't matter.
- 2,000 twos followed by three zeros → false, and plain recursion tries a huge number of paths before saying so.
practise next
Similar problems
- #45Jump Game IIMediumin Greedy
- #763Partition LabelsMediumin Greedy