Minimum Jumps to End
Medium · Dynamic Programming · Array · Dynamic Programming · Greedy
Problem
You start at index 0 of an integer array nums. From index i you may jump forward to any index i + j with 1 <= j <= nums[i], staying inside the array.
Return the fewest jumps needed to reach the last index, n - 1. The tests guarantee that the last index can be reached.
Examples
Input: nums = [3,1,1,1,4,2] Output: 3
For example 0 → 3 → 4 → 5. Two jumps cannot do it: one jump reaches at most index 3, and from indices 1 to 3 a second jump reaches at most index 4.
Input: nums = [4,1,1,3,1] Output: 1
A single jump of 4 lands on the last index.
Input: nums = [5] Output: 0
You start on the last index.
Constraints
- 1 <= len(nums) <= 10^4
- 0 <= nums[i] <= 1000
- The last index is always reachable
Approaches
- Baseline: fewest jumps to every cell — time O(n · max(nums)), space O(n)
Follow-up
What if the end might be unreachable, or each cell allowed exactly one jump length in either direction? See the use cases “Fewest jumps, or -1 when stuck” and “Fewest jumps of exact length, either way”. If each jump also had a cost, the greedy breaks and a shortest-path table is needed.
Related problems
Start free on Cariara · Coding problems · System design studio
