Learning Outcome
After this lesson, you should be able to turn many possible jump paths into one farthest-reach invariant.
Problem Statement
Given an array where nums[i] is the maximum jump length from index i, return true if you can reach the last index.
| Input | Output | Why |
|---|---|---|
nums = [2,3,1,1,4] | true | Index 0 can reach index 1, and index 1 can reach the end. |
Brute Force Approach
Try every possible jump path recursively. This repeats states and can become exponential.
Optimized Approach
Scan left to right and maintain the farthest reachable index. If the current index is beyond farthest, the end is impossible.
Exact Pseudocode
farthest = 0
for i from 0 to n - 1:
if i > farthest:
return false
farthest = max(farthest, i + nums[i])
return trueReference Code
class Solution:
def canJump(self, nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return TrueSample Dry Run
| Step | State | Result |
|---|---|---|
| i = 0 | farthest = max(0, 0 + 2) | farthest = 2 |
| i = 1 | 1 is reachable, update with 1 + 3 | farthest = 4 |
| i = 2,3,4 | All are within farthest | End is reachable |
| Return | No unreachable index found | true |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each index is checked once. |
| Space | O(1) | Only the farthest reachable index is stored. |
Edge Cases
- A single-element array is already reachable.
- If i becomes greater than farthest, return false immediately.
- Zeros are fine unless they block all future progress.
Interview Checklist
- Check reachability before using nums[i].
- Update farthest with i + nums[i].
- Do not explore every path once the invariant is known.
FAQs
Why is farthest enough?
If an index is reachable, only the best future reach matters; the exact path no longer matters.
When do we fail?
We fail when the scan reaches an index greater than the farthest reachable index.
What is the core pattern?
Farthest-reach greedy.