Jump Game II
Problem 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 <= 104
0 <= nums[i] <= 1000- It's guaranteed that you can reach
nums[n - 1].
Solve it on LeetCode
Approaches
1. Greedy Approach
Intuition:
The first solution is a simple greedy approach. The idea is to make the best move we can at each index. We traverse the array and at each step, we jump to the farthest position possible within the range of our current jump. By making the best move at each step (jumping the farthest possible), we ensure that we reach the end in the minimum number of jumps.
Approach:
- Start from the first position of the array and attempt to reach the last position with the minimum number of jumps.
- Use variables:
jumpsto count the number of jumps.curEndto track the farthest index that can be reached with the current number of jumps.curFarthestto track the farthest index that we could reach with an additional jump within the range ofcurEnd.- Whenever we move beyond
curEnd, it means we need to make a jump, so updatejumpsandcurEnd.
Code:
- Time Complexity: O(n), since we are making a single pass through the array.
- Space Complexity: O(1), as no extra space is used.
2. Optimized Greedy Approach
Intuition:
In the optimized version of the greedy approach, we maintain only necessary variables to track the farthest reachable point and leverage this to calculate the minimum jumps on the go. By focusing on optimizing jump increments logically with conditions, this approach refines the previous solution for simplicity without affecting time complexity.
Approach:
- Similar to the first approach but is less explicitly managed with retained focus on optimal point reachability only.
Code:
- Time Complexity: O(n), iterating through the array once as before.
- Space Complexity: O(1), no extra space apart from variables.