LC 0045 [M] Jump Game II - ALawliet/algorithms GitHub Wiki

prereq: Level Order Traversal, Jump Game

---

it's more BFS than greedy, but we do look for the max at each level

each jump represents going to the next level after checking the current options

we go to the next level after we've checked the best max we can get from up to the current position so far (it may have come from a previous step)

e.g. from 0 we can jump to 1 or 2, the furthest at that point local_max_pos we can go is 2, but after we find that if we stopped at 1 instead we can jump all the way to 4 after which becomes the global_max_pos, then after that we check from 2 and we can only go to 3 local_max_pos so it doesn't update the global_max, so it's like checking in between from that index up to and including the previously found furthest jump to see if we can do better

jumps=1
start=0 end=0
i=0 level_size=0 local_max=2 global_max_pos=2
--------------------------------------level 1
jumps=2
start=1 end=2
i=1 level_size=2 local_max=4 global_max_pos=4
start=2 end=2
i=2 level_size=2 local_max=3 global_max_pos=4
--------------------------------------level 2

0 1 2 3 4
2 3 1 1 4

start 0
    2
☻-->|
--------------------------------------level 1
start 1,2
        4
  ☻---->|
      3
    ☻->
--------------------------------------level 2

https://www.youtube.com/watch?v=dJ7sWiOoK7g&ab_channel=NeetCode

BFS O(n)

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        l = r = 0 # r is global max
        
        while r < len(nums) - 1: # 2nd to last
            farthest = 0 # level size = r = global max, or just 0
            for i in range(l, r+1):
                farthest = max(farthest, i + nums[i]) # local max
            l, r = r + 1, farthest # level window

            jumps += 1
            
        return jumps
            

class Solution:
    def jump(self, nums: List[int]) -> int:
      global_max_pos = 0
      jumps = 0
      start = 0

      while global_max_pos < len(nums) - 1:
          level_size = global_max_pos

          jumps += 1
          # print(f'jumps={jumps}')

          for i in range(start, level_size + 1):
              # print(f'start={start} end={level_size + 1 - 1}')
              local_max_pos = i + nums[i]
              global_max_pos = max(global_max_pos, local_max_pos)
              start += 1
              # print(f'i={i} level_size={level_size} local_max={local_max_pos} global_max_pos={global_max_pos}')

          # print(f'--------------------------------------level {jumps}')

      return jumps