Leetcode # 2856. Minimum Array Length After Pair Removals

Problem

https://leetcode.com/problems/minimum-array-length-after-pair-removals

Testcases

Failed Solution: Greedy 
[Wrong Answer  338 / 635 testcases passed]

Failed case: [1,1,2,3,4,4]

class Solution:
  def minLengthAfterRemovals(self, nums: List[int]) -> int:
    counter = Counter(nums)
    remained = sorted(counter.keys())
    
    def find_i(nums, num, left=0, right=-1):
      right = (right + len(nums)) % len(nums)
      while left < right:
        mid = (left + right) // 2
        if nums[mid] < num: left = mid + 1 
        else: right = mid
      return left

    def delete(num, i):
      nonlocal counter, remained
      counter[num] -= 1
      if counter[num] == 0:
        remained.pop(i)
    
    for num in nums[::-1]:
      if num not in remained or remained[0] >= num:
        continue
      i = find_i(remained, num)
      delete(num, i)
      delete(remained[i - 1], i - 1)
    return sum([counter[num] for num in remained])

Solution: Mathematics

\begin{align}
\text{令 } nums := & [N_{L, \ 1}, N_{L, \ 2}, N_{L, \ 3}, …, N_{L, \ n_L}]\\
& + [N_a] * n_a + [N_{R, \ 1}, N_{R, \ 2}, N_{R, \ 3}, …, N_{R, \ n_R}]
\end{align}

∀ N_{L, i}, N_{R, j} != N_a
因為 nums 為 non-decreasing ⇒ ∀ N_{L, i} < N_a ∧ ∀ N_{R, j} > N_a
⇒ N_a 可以和任意的 N_{L, i}  和 N_{R, j} 配對刪除

1. 如果nums裡只有一種數字(len(set(nums)) == 1)
   ⇒ 沒法消 ⇒ len(nums)
2. nums裡的數字種類為複數：
   1. nums中數量最多的數字其數量超過nums長度的一半
      ≡ 有一個數字把其他數字都消完了還會剩下
      ⇒ 消完所有其他數字後剩下2 * max(Counter(nums).values()) - len(nums))
   2. 所有nums裡的數字數量都不超過nums長度的一半
      ⇒ 如果len(nums)為偶數則能全部消除，若為奇數則有 1 個數字無法被配對

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

class Solution:
  def minLengthAfterRemovals(self, nums: List[int]) -> int:
    return len(nums) if len(set(nums)) == 1 else max(len(nums) % 2, 2 * max(Counter(nums).values()) - len(nums))

Refined Solution: Mathematics

if len(set(nums)) == 1: return len(nums)
⇒ 併入 2 * (bisect.bisect_right(nums, nums[len(nums) // 2]) - bisect.bisect_left(nums, nums[len(nums) // 2])) - len(nums)

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

class Solution:
  def minLengthAfterRemovals(self, nums: List[int]) -> int:
     return max(len(nums) % 2, 2 * (bisect.bisect_right(nums, nums[len(nums) // 2]) - bisect.bisect_left(nums, nums[len(nums) // 2])) - len(nums))

Last Updated on 2023/09/22 by A1go