You have an array where each element is a non-negative integer. Starting at index 0, the value at index i tells you the maximum number of positions you can jump forward from there. Determine whether you can reach the last index.
This is LeetCode 55, “Jump Game”, and it is the canonical introduction to greedy thinking in the modern interview canon. The DP solution is straightforward and gets partial credit. The greedy O(n) one-pass solution requires recognizing that you can solve the problem by tracking only “the farthest position reachable so far” and updating that as you iterate. Once a candidate has internalized this insight on Jump Game, the related greedy problems (Jump Game II, Gas Station, Best Time to Buy and Sell Stock) become accessible.
Examples
nums = [2, 3, 1, 1, 4]
Output: True
(jump 1 step from 0 to 1, then 3 steps from 1 to 4)
nums = [3, 2, 1, 0, 4]
Output: False
(stuck at index 3 since nums[3] = 0)
Solution 1: DP, O(n²)
def can_jump_dp(nums):
n = len(nums)
reachable = [False] * n
reachable[0] = True
for i in range(n):
if not reachable[i]:
continue
for jump in range(1, nums[i] + 1):
if i + jump < n:
reachable[i + jump] = True
return reachable[n - 1]
Mark each reachable index, propagate forward from each. O(n²) time, O(n) space. Correct, gets partial credit.
Solution 2: greedy from the right, O(n)
def can_jump_back(nums):
last_good = len(nums) - 1
for i in range(len(nums) - 1, -1, -1):
if i + nums[i] >= last_good:
last_good = i
return last_good == 0
Start from the last index, treating it as the “good” position. Walk backward; for each index, check if from there you can jump to a known good position. If yes, mark it as good. At the end, check if index 0 is good. O(n) time, O(1) space.
Solution 3: greedy from the left, O(n)
def can_jump(nums):
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False
farthest = max(farthest, i + nums[i])
return True
Track the farthest position reachable so far. Iterate forward; for each index, if it is past the current farthest, we can never reach it, so return False. Otherwise, update the farthest reachable. O(n) time, O(1) space.
This is the cleanest version. Six lines. The whole insight is: at each step, we only need to know “what is the farthest I can reach”, not the full set of reachable positions. The greedy update is “max(current, i + nums[i])”.
Why the greedy works
The argument is short. Suppose the algorithm declares the last index unreachable. That means at some point, i > farthest, which means no earlier index could jump to position i or beyond. So position i is unreachable, and so is the last position. Conversely, if the algorithm completes without returning False, then every index up to and including the end was reachable from earlier — the farthest expanded to cover the entire array. Done.
The greedy works because the structure of the problem is monotonic: the set of reachable positions only grows as you iterate forward. You never need to revisit an earlier position; just track the boundary of reachability.
Why Jump Game became canonical
Jump Game is famous in the modern canon for three reasons:
- Clean greedy invariant. The “farthest reachable” invariant is the simplest non-trivial greedy invariant in the LeetCode canon. Once a candidate sees it, they recognize it in many other problems.
- Two acceptable greedy directions. Both “greedy from the right” and “greedy from the left” are correct and instructive. The choice between them depends on the candidate’s preference; both produce O(n) solutions.
- Generative for related problems. Jump Game II (minimum jumps to reach the end), Best Time to Buy and Sell Stock (greedy max profit), Gas Station (find a starting station), and many other problems use similar greedy structures. Internalizing Jump Game opens the family.
The greedy pattern
The greedy pattern is: at each step, make the locally-optimal choice; the local optima compose into a global optimum because of some monotonic structure in the problem. Greedy works on a relatively small subset of problems, but on those problems it is dramatically faster than DP. Other canonical greedy problems:
- Jump Game II (LC 45) — minimum jumps to reach the end
- Gas Station (LC 134) — find a starting position
- Best Time to Buy and Sell Stock (LC 121) — single-transaction max profit
- Maximum Subarray (LC 53) — Kadane’s algorithm; greedy + DP hybrid
- Task Scheduler (LC 621) — greedy with cooldown
- Meeting Rooms II (LC 253) — greedy interval scheduling
Recognizing whether a problem admits a greedy solution is a senior-level skill. The proof of correctness — “exchange argument” or “stay ahead” — is what separates strong candidates from those who just guess that greedy might work.
What interviewers grade
Jump Game is a phone-screen-tier problem (medium difficulty). The bar is the O(n) greedy solution within the slot. Signal layers:
- State the DP solution first. Most candidates produce this in 5 minutes.
- Recognize the greedy opportunity. “I do not need the full reachability set; I just need the farthest reachable position.”
- Argue correctness. Why does the greedy work? Sketch the monotonicity argument.
- Clean code. Six lines for the forward greedy; no off-by-ones.
- Stretch follow-up: Jump Game II. Now find the minimum number of jumps to reach the end. The greedy still works; the implementation is a step harder.
Variations interviewers ask
- Jump Game II (LC 45). Minimum number of jumps. BFS-like greedy that tracks current and next “frontier” of reachable positions.
- Jump Game III (LC 1306). Each cell has both forward and backward jump distances. BFS / DFS instead of pure greedy.
- Jump Game IV (LC 1345). Cells can also jump to other cells with the same value. BFS over an implicit graph.
- “What is the minimum value modification to make it always reachable?” Inverse problem; harder.
Is it asked in 2026?
Yes, frequently at FAANG phone screens and tier-2 tech onsites. Jump Game is in the LeetCode top 50 most-asked Mediums and is one of the most common greedy-pattern problems. The follow-up Jump Game II is a natural senior+ extension, and the broader greedy family makes the question generative.
Frequently Asked Questions
What is the time complexity of the optimal solution?
O(n). One pass through the array.
What is the space complexity?
O(1). Just a single integer for the farthest reachable position.
Why does the greedy work?
Because the set of reachable positions only grows monotonically as you iterate forward. You never need to revisit earlier positions; just track the boundary.
Should I solve from the left or from the right?
Either works. The forward (left-to-right) version is slightly more conventional and slightly easier to extend to Jump Game II. Both produce O(n) solutions.
Is this still a useful interview question?
Yes. It is the canonical introduction to greedy thinking, and the related problems make it a generative question even when the candidate has seen the basic version.