45. Jump Game II
DifficultyMedium
Description
You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:
0 <= j <= nums[i]andi + j < n
Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.
Example 1:
Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4] Output: 2
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1000- It's guaranteed that you can reach
nums[n - 1].
Solutions
Solution 1: Greedy Algorithm
Thinking
The first idea is DP: \(f[i]\) is the fewest jumps to \(i\), and from \(i\) we relax \(i+1..i+\textit{nums}[i]\). Correct, worst-case \(O(n^2)\). \(n \le 10^4\) may pass, but we only need the end, not a value at every index.
The bottleneck is maintaining exact min jumps per position. Jump \(k\) covers a contiguous range; the farthest we can see inside it is the right end of jump \(k+1\).
Scan once, tracking this jump's boundary and the farthest the next jump can reach. Hitting the boundary forces a jump. That is BFS by layers without a queue.
We can use a variable \(mx\) to record the farthest position that can be reached from the current position, a variable \(\textit{last}\) to record the position of the last jump, and a variable \(\textit{ans}\) to record the number of jumps.
Next, we traverse each position \(i\) in \([0,..n - 2]\). For each position \(i\), we can calculate the farthest position that can be reached from the current position through \(i + \textit{nums}[i]\). We use \(mx\) to record this farthest position, that is, \(mx = \max(mx, i + \textit{nums}[i])\). Then, we check whether the current position has reached the boundary of the last jump, that is, \(i = \textit{last}\). If it has reached, then we need to make a jump, update \(\textit{last}\) to \(mx\), and increase the number of jumps \(\textit{ans}\) by \(1\).
Finally, we return the number of jumps \(\textit{ans}\).
The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.
Similar problems:
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |