Leetcode # 2616. Minimize the Maximum Difference of Pairs

https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs

Solution: Greedy Method + Binary Search

Greedy Method – count_valid_pairs(threshold)

count_valid_pairs(threshold): 

1. 事先已將nums排序過
2. i = 0, 1, 2, …, n – 2
   如果nums[i]和nums[i + 1]的差距 <= threshold
   則將兩者配成一對
3. 回傳成對的數量

count_valid_pairs(threshold)是一個遞增函式
所以我們要利用 binary search
並且是 duplicate elements, left-most insertion point 的pattern
找出符合能達成「配對數量 >= p」條件的的最小 threshold

Code

Time Complexity: O(n * log(n) + log(max(nums) – min(nums)))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minimizeMax(self, nums: List[int], p: int) -> int:
    nums.sort()
    n = len(nums)

    def count_valid_pairs(threshold):
      i = count = 0
      while i < n - 1:
        if nums[i + 1] - nums[i] <= threshold:
          count += 1
          i += 1
        i += 1
      return count

    left, right = 0, nums[-1] - nums[0]
    while left < right:
      mid = (left + right) // 2
      pairs_n = count_valid_pairs(mid)
      if pairs_n >= p:
        right = mid
      else:
        left = mid + 1
    return left

Last Updated on 2023/08/16 by A1go