Jump Game II

[fbaquant]

https://leetcode.com/problems/jump-game-ii/

Very well explained solution https://www.youtube.com/watch?v=dJ7sWiOoK7g

[fbaquant]

class Solution:
    def jump(self, nums: List[int]) -> int:
        l = 0
        r = 0
        max_r = 0
        jumps = 0

        while r < len(nums) - 1:
            for i in range(l, r + 1):
                max_r = max(i + nums[i], max_r)
            l = r + 1
            r = max_r
            jumps += 1
        return jumps

[AYoonOh]

class Solution:
    def jump(self, nums: List[int]) -> int:
        idx, jump, curr, farthest = 0, 0, 0, 0
        while curr < len(nums)-1:
            farthest = max(farthest, nums[idx] + idx)
            if idx == curr: jump += 1; curr = farthest
            idx += 1
        return jump

[kangjh0722]

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

    j, j_max = 0, 0

    # Implicit BFS
    for i in range(len(nums) - 1):
      if i + nums[i] > j_max:
        j_max = i + nums[i]

      if j_max >= len(nums) - 1:
        jump_count += 1
        break

      if i == j:             # Visited all the items on the current level
        jump_count += 1      # Increment the level
        j = j_max            # Make the queue size for the next level

    return jump_count