DSA problem
Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i, so you can jump to any index i + j where 1 <= j <= nums[i] and i + j < n. Return the minimum number of jumps to reach n - 1. The test cases are generated such that you can always reach the last index.
A classic dynamic-programming solution computes the minimum jumps to each index in O(n^2) time. The greedy reformulation reduces this to O(n) by realizing the problem is implicitly a Breadth-First Search on the array, where each "level" is the set of indices reachable in the same number of jumps.
Maintain three variables: jumps (the answer so far), currentEnd (the rightmost index in the current BFS level), and farthest (the farthest index any position in the current level can reach). As you scan, farthest = max(farthest, i + nums[i]). When the iteration index i reaches currentEnd, you have exhausted the current level: increment jumps and promote currentEnd to farthest, opening the next BFS level.
The algorithm walks indices 0 through n - 2 (you do not need to jump from the last index — you have already arrived). This is provably optimal because every position in the current level shares the same jump count, so taking the maximum reach across them gives the maximum reach of the next level. Time complexity is O(n) and space is O(1).
Examples
nums = [2,3,1,1,4]2nums = [2,3,0,1,4]2nums = [1,2,1,1,1]3Constraints
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000
- It is guaranteed that you can reach nums[n - 1].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.