Jump Game II
- 2 min read
- Greedy
- LC-Medium
3 years ago
Solution
- Look at Jump Game before this.
- We can solve this using a Breadth-first Search on the array
- There first element is the first "level"- i.e. 0 jumps needed to reach.
- Every other index we can reach from the first index, is the second "level".
- We need to keep track of how many times we do the breadth first search. This will be our answer.
- We use two pointers
landrto keep track of our current window of values, i.e. there are 2 levels after the first one below, andlandrwill be used to keep track of the values - Initially,
landrare 0 - At each iteration, we get the farthest index that can be moved to from the current level, let's call this
farthest:- We then move the window to represent moving to the level of breadth first search:
- Set the value of
ltor + 1 - Set the value of
rtofarthest - Increment
ans- our variable containing number of jumps / number of BFSs
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def jump(self, nums: List[int]) -> int:
l = r = ans = 0
while r < len(nums) - 1:
farthest = 0 # Doesn't matter if it's 0 or -math.inf. It's just an initializer value
for i in range(l, r + 1):
farthest = max(farthest, i + nums[i])
l = r + 1
r = farthest
ans += 1
return ans