Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^5
Examples:
Input: [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 index 1, then 3 steps to index 4.
Solutions
Greedy
We use a greedy approach to solve this problem. We maintain three variables: maxReach, step, and jumps. maxReach stores the maximum reachable index, step stores the current step, and jumps stores the number of jumps. We iterate through the array and update maxReach and step accordingly. If we reach the end of the current step, we increment jumps and update step to maxReach.
def jump(nums):
max_reach, step, jumps = 0, 0, 0; for i in range(len(nums) - 1):
max_reach = max(max_reach, i + nums[i]); if i == step:
jumps += 1; step = max_reach; return jumpsFollow-up:
What if we can jump backwards?
