Greedy — Jump Game
↗ LeetCode: Jump Game · Medium · pattern chapter →
Asked atMetaAmazonGoogleMicrosoftBloomberg
nums[i] = max jump length from i. Return true iff we can reach the last index starting from index 0.
Example 1 — nums=[2,3,1,1,4] → trueExample 2 — nums=[3,2,1,0,4] → falseExample 3 — nums=[0] → true
Constraints — 1 ≤ n ≤ 10⁴. Brute DP tries every reachable index from each position — O(n²) = 10⁸ ops at n=10⁴. Greedy running-max-reach is O(n) = 10⁴ ops = <1 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — DP reachable[i]
O(n²). Baseline.
Approach 2 — Greedy farthest reach (canonical)
Insight. Track maxReach = max(i + nums[i]). At index i, if i > maxReach, we're stuck. Update as we go.
java
boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}Execution Trace
Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| DP reachable | O(n²) | O(n) | baseline |
| Greedy | O(n) | O(1) | canonical |
When to use which
- Reachability only → greedy.
- Min jumps → Jump Game II — BFS layers.
- Arbitrary graph jumps → Jump Game III — BFS.
AI Study CompanionBeta
Related problems
Was this page helpful?