Dynamic Programming · LC #55
Jump Game
Greedily track the farthest index reachable as you scan left to right. If the current index ever exceeds the farthest reach, the end is unreachable; otherwise return true after a full scan.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given array `nums` where `nums[i]` is the maximum jump length from index `i`, determine if you can reach the last index starting from index 0.
Sample I/O
Input: nums = [2,3,1,1,4] Output: true Input: nums = [3,2,1,0,4] Output: false
Intuition
How to Think About It
Intuition
At every position we just need to know the farthest index we could have reached so far. If the current position is within that frontier, we can stand there and potentially extend it further.
Core Concept
Single pass: maintain `maxReach`. For each index `i`: if `i > maxReach` return false (can't reach here). Otherwise `maxReach = max(maxReach, i + nums[i])`. If the loop completes, return true.
When to use
Reachability problems on linear arrays where each position grants a bounded forward reach. Also a building block for Jump Game II (minimum jumps).
When NOT to use
When you need the minimum number of jumps (greedy with BFS levels - LC 45). When jumps can go backwards. When positions have costs that affect feasibility.
Key Insights
What to Know Cold
- O(1) space greedy beats O(n) DP - no dp array needed; a single integer suffices.
- The greedy invariant: if index i is reachable, every index ≤ i is also reachable.
- Once maxReach ≥ n-1, the last index is guaranteed reachable; can return early.
- A zero value at index i is only a trap if i == maxReach (no other path can bypass it).
- This greedy approach works because all jump values are non-negative - backward jumps would break it.
1 example
Worked Examples
Can robot reach end of [2,3,1,1,4]?
From index 0, max jump = 2; trace the maximum reachable frontier.
Greedy scan tracking maxReach; short-circuit on blocked position.
Output: true
Tests the ability to recognise when a greedy approach dominates DP; interviewers at Amazon and Google expect O(1) space, not the O(n) DP table approach.