Leetcode # 632. Smallest Range Covering Elements from K Lists

Problem

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists

Solution: Sliding Window
[Time Limit Exceeded  86 / 88 testcases passed]

all_nums := list(itertools.chain.from_iterable(nums))
max_num := max(all_nums)
min_num := min(all_nums)
m := len(nums)
n := len(all_nums)

Time Complexity: O((max_num – min_num) * m)
Space Complexity: O(m)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def smallestRange(self, nums: List[List[int]]) -> List[int]:
    left = min([nums_[ 0] for nums_ in nums])
    end  = max([nums_[-1] for nums_ in nums])
    ans = [left, end]
    pointers = [0 for _ in nums]
    for right in range(left, end + 1):
      for i, nums_ in enumerate(nums):
        while pointers[i] < len(nums_) - 1 and nums_[pointers[i] + 1] <= right:
          pointers[i] += 1

      if all(left <= nums_[pointers[i]] <= right for i, nums_ in enumerate(nums)):
        left = min([nums_[pointers[i]] for i, nums_ in enumerate(nums)])
        if right - left < ans[1] - ans[0]:
          ans = [left, right]
      
    return ans

Solution: Using Pointers
[Time Limit Exceeded  86 / 88 testcases passed]

每個 nums[i] 分配一個 pointers[i]
pointers[i] 從 index 0 開始
每次從尚未到終點的 pointers[i] 中
選取其值 nums[i][pointers[i]] 最小者
將其向後移動 1 
若有一 pointers[i] 遍歷至終點
則終止 while loop (參考 Solution: Priority Queue – 2.)

Time Complexity: O(n * m)
while loop 執行 n 次
每一次 while loop 中 執行 m 次的 for loop
Space Complexity: O(m)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def smallestRange(self, nums: List[List[int]]) -> List[int]:
    first_elements = [nums_[0] for nums_ in nums]
    ans = [min(first_elements), max(first_elements)]
    pointers = [0] * len(nums) # [-1] + [0] * (len(nums) - 1)
    next_moved_i = 0
    # while loop: n times
    # while next_moved_i >= 0: 
    while pointers[next_moved_i] < len(nums[next_moved_i]): 
      
      # pointers[next_moved_i] += 1 # this line is moved to bottom

      # find min_num and max_num, m times
      # min_can_be_moved, next_moved_i = inf, -1
      min_num, max_num = inf, -inf
      for i, nums_ in enumerate(nums): # m times
        num = nums_[pointers[i]]

        # update min_num
        # min_num = min(min_num, num)
        if num < min_num:
          min_num, next_moved_i = num, i
        max_num = max(max_num, num)
        """
        if pointers[i] < len(nums_) - 1 and num < min_can_be_moved:
          min_can_be_moved = num
          next_moved_i = i
        """
      # update ans
      if max_num - min_num < ans[1] - ans[0]:
        ans = [min_num, max_num]
      
      pointers[next_moved_i] += 1 # moved from line 10
      
    return ans

Solution: Priority Queue

Python 請參考 heapq

1. pop 掉最小的heap[0]≡nums[i][j]
   再將其之後的nums[i][j + 1] push 進heap替換它
   （這和上一個 solution 的做法是一樣的
   但是改用 priority queue 使時間複雜度從 O(m) 減少至 O(log(m))）
2. 當nums[i]已被遍歷至底
   就沒有繼續向後遍歷其他nums[k] (k != i) 的必要
   因為如此要包含nums[i][j]及其他元素 num_k ∈ nums[k] 的閉區間只可能越來越大
3. 關於max_num：
   1. 當 heap 中的最大值nums[i][j]=max_num被 pop 出
      但因為所有nums[i]為 non-decreasing order
      故用以替代的下一個nums[i][j + 1]必定>= nums[i][j]=max_num
nums[i][j + 1]會成為新的max_num
   2. 若無下一個 num，根據 2. 則結束 while loop

Time Complexity: O(m + n * log(m)) = O(n * log(m))
Space Complexity: O(m)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def smallestRange(self, nums: List[List[int]]) -> List[int]:
    m = len(nums)
    heap = []
    max_num = -inf
    # O(m)
    for i in range(m):
      heappush(heap, (nums[i][0], i, 0))
      max_num = max(max_num, nums[i][0])

    # heap[0][0] ≡ min(heap)[0]
    ans = [heap[0][0], max_num]
    while True: # O(n)
      print([h[0] for h in heap])
      # pop 掉最小的 heap[0] ≡ nums[i][j]
      _, i, j = heappop(heap) # O(log(m))
      if (j := j + 1) == len(nums[i]):
        break
      next_num = nums[i][j]
      # 如果新的值比原最大值更大則替換
      max_num = max(max_num, next_num)
      # 推入 nums[i][j + 1] 替代被 pop 掉的 nums[i][j]
      heappush(heap, (next_num, i, j)) # O(log(m))
      if max_num - heap[0][0] < ans[1] - ans[0]:
        ans = [heap[0][0], max_num]
      
    return ans

Last Updated on 2023/09/06 by A1go