Jump Game II
LeetCode #45 · Medium · Greedy · C++ solution with worked-out approach and complexity analysis.
Approach
Greedy - BFS-like Level Traversal
Key insight
Think of this as finding the minimum levels in a BFS traversal. Each "level" represents positions reachable with the same number of jumps.
Strategy
- 1Track currentEnd: the farthest position reachable with current number of
- 2Track maxPosition: the farthest position we can reach from any position
- 3When we reach currentEnd, we must make another jump (increment jumps)
- 4Update currentEnd to maxPosition (start exploring the next "level")
- 5Stop when currentEnd reaches or exceeds the last index
Time
O(n)
single pass through the array
Space
O(1)
only using a few variables
Problem description(from LeetCode)
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. Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Examples
Example 1
- Input:
- nums = [2,3,1,1,4]
- Output:
- 2
- Note:
- 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. Input: nums = [2,3,0,1,4] Output: 2
Constraints
- •1 <= nums.length <= 10^4
- •0 <= nums[i] <= 1000
- •It's guaranteed that you can reach nums[n - 1].
C++ Solution
solution.cpp
class Solution {
public:
int jump(vector<int> &nums) {
int maxPosition = 0, n = nums.size(), jumps = 0, currentEnd = 0;
if (n == 1) return 0;
for (int i = 0; i < n; i++) {
maxPosition = max(maxPosition, i + nums[i]);
if (i >= currentEnd) {
currentEnd = maxPosition;
jumps++;
}
if (currentEnd >= n - 1) break;
}
return jumps;
}
};