Topic · GreedyMedium
Jump Game
Understand the problem
Given an array nums, where nums[i] is the maximum number of steps you can jump from cell i.
Starting at cell 0, return true if you can reach the last cell.
ts
nums = [2,3,1,1,4] → true // 0→1→4 or 0→2→3→4
nums = [3,2,1,0,4] → false // stuck at the cell with value 0, cannot get past itThe greedy idea: scan from right to left, keeping track of the closest goal that can be reached.
- If you can jump from cell i to that goal, i becomes the new goal.
- At the end, check whether the goal has moved back to cell 0.
Basic approach
O(n²) time, O(n) spacets
function canJumpDP(nums: number[]): boolean {
const n = nums.length
const reachable = new Array(n).fill(false)
reachable[n - 1] = true
for (let i = n - 2; i >= 0; i--) {
// try every jump length from cell i
for (let step = 1; step <= nums[i]; step++) {
if (reachable[i + step]) { reachable[i] = true; break }
}
}
return reachable[0]
}Why this approach is slow:
This approach tries every possible jump from each cell and stores a "can I reach the end from here" table → O(n²).
Tracking a single variable for the closest goal is enough, which brings it down to O(n) time and O(1) space.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.