Given an array of non-negative integers nums, 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.
You can assume that you can always reach the last index.
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 <= 10^40 <= nums[i] <= 1000
The description was taken from https://leetcode.com/problems/jump-game-ii/.
#O(N) Time, O(1) Spaceclass Solution: def jump(self, nums: List[int]) -> int: min_jumps = max_jump = left = right = 0 while right < len(nums)-1: for i in range(left, right+1): max_jump = max(max_jump, i + nums[i]) left = right + 1 right = max_jump min_jumps += 1 return min_jumpsWe can solve this problem with a greedy, Breadth-First Search type algorithm.
A good indication that this is a greedy problem is when the description states we are trying to do something in the minimum number of steps possible. To do that, we will want to collect the greatest values so that we can cover the most distance in the shortest amount of time. This way, we can be greedy with our jumps and only do them when absolutely necessary.
That is where the Breadth-First Search aspect comes in. We will start from the beginning of the index, cash in our jump points to get a little further then continuously gain the maximum jump points for each group we can get within range of.
We'll start by initializing our minimum jumps output, our running max jump value, and both of our pointers at zero.
min_jumps = max_jump = left = right = 0
While the right pointer hasn't reached the end of the array, we will need to continue collecting the greatest jump points that will get us to the end of the array.
while right < len(nums)-1:
To do that, we will search within the current range that is within our jump point budget.
This range is between the left and right pointers, inclusive.
for i in range(left, right+1):
We will compare the current jump point value, which will be the current index plus its value, with the best we have so far.
By including the current index plus its value, we are ensuring that we are only getting jump points that will benefit us within each additional step. For example, if we have four jump points at index one, that won't be as useful to us as two jump points at index four.
max_jump = max(max_jump, i+nums[i])
After looking for the best jump points within the index we are able to venture to, we will continue to a new range beginning where the right pointer was last at and ending with the greatest jump we can make so far.
left = right + 1 right = max_jump
Each time we venture to a new range, we will make one additional jump.
min_jumps += 1
Once we are finished, we will return the minimum number of jumps we had to make.
return min_jumps
This is why this question is a sort of Breadth-First Search, each greatest value will unlock a new group we can jump to, and we will need to search each group for the new greatest max jump value in order to get to the end of the array in the least amount of jumps.
If we were to split up these groups it would look like this:
[2,3,1,1,4,3,5,2]
We'd have two jump points, venture to the two jumps within our jump point budget then collect three jump points at index one, venture to three jumps within our jump budget then collect four jump points at index four, then those would be enough for us to reach the end of the array. If it weren't though, we'd have that juicy five at index six we would collect next.