Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def jump(self, arr: List[int]) -> int:
- # If only one element, already at the end
- if len(arr) == 1 or arr[0] == 0:
- return 0
- l = 0 # left boundary of current jump range
- r = 0 # right boundary of current jump range
- jumps = 0
- # Continue until the last index is reachable
- while r < len(arr) - 1:
- farthest = r # farthest index reachable in the next jump
- # Explore all indices in the current range [l, r]
- for i in range(l, r + 1):
- # From index i, try to extend the reach
- farthest = max(farthest, i + arr[i])
- # Move to the next jump range
- l = r + 1
- r = farthest
- # One jump completed
- jumps += 1
- return jumps
Advertisement
Add Comment
Please, Sign In to add comment