Question

2856. Minimum Array Length After Pair Removals

中文文档

Description

You are given a 0-indexed sorted array of integers nums.

You can perform the following operation any number of times:

• Choose two indices, i and j, where i < j, such that nums[i] < nums[j].
• Then, remove the elements at indices i and j from nums. The remaining elements retain their original order, and the array is re-indexed.

Return _an integer that denotes the minimum length of _nums_ after performing the operation any number of times (including zero)._

Note that nums is sorted in non-decreasing order.

 

Example 1:

Input: nums = [1,3,4,9]
Output: 0
Explanation: Initially, nums = [1, 3, 4, 9].
In the first operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 1 < 3.
Remove indices 0 and 1, and nums becomes [4, 9].
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 4 < 9.
Remove indices 0 and 1, and nums becomes an empty array [].
Hence, the minimum length achievable is 0.

Example 2:

Input: nums = [2,3,6,9]
Output: 0
Explanation: Initially, nums = [2, 3, 6, 9]. 
In the first operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 2 < 6. 
Remove indices 0 and 2, and nums becomes [3, 9]. 
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 3 < 9. 
Remove indices 0 and 1, and nums becomes an empty array []. 
Hence, the minimum length achievable is 0.

Example 3:

Input: nums = [1,1,2]
Output: 1
Explanation: Initially, nums = [1, 1, 2].
In an operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 1 < 2. 
Remove indices 0 and 2, and nums becomes [1]. 
It is no longer possible to perform an operation on the array. 
Hence, the minimum achievable length is 1. 

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• nums is sorted in non-decreasing order.

Solutions

Solution 1: Greedy + Priority Queue (Max Heap)

We use a hash table $cnt$ to count the occurrence of each element in the array $nums$, then add each value in $cnt$ to a priority queue (max heap) $pq$. Each time we take out two elements $x$ and $y$ from $pq$, decrease their values by one. If the value after decrement is still greater than $0$, we add the decremented value back to $pq$. Each time we take out two elements from $pq$, it means we delete a pair of numbers from the array, so the length of the array decreases by $2$. When the size of $pq$ is less than $2$, we stop the deletion operation.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def minLengthAfterRemovals(self, nums: List[int]) -> int:
    cnt = Counter(nums)
    pq = [-x for x in cnt.values()]
    heapify(pq)
    ans = len(nums)
    while len(pq) > 1:
      x, y = -heappop(pq), -heappop(pq)
      x -= 1
      y -= 1
      if x > 0:
        heappush(pq, -x)
      if y > 0:
        heappush(pq, -y)
      ans -= 2
    return ans

class Solution {
  public int minLengthAfterRemovals(List<Integer> nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer::sum);
    }
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    for (int x : cnt.values()) {
      pq.offer(x);
    }
    int ans = nums.size();
    while (pq.size() > 1) {
      int x = pq.poll();
      int y = pq.poll();
      x--;
      y--;
      if (x > 0) {
        pq.offer(x);
      }
      if (y > 0) {
        pq.offer(y);
      }
      ans -= 2;
    }
    return ans;
  }
}

class Solution {
public:
  int minLengthAfterRemovals(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (int x : nums) {
      ++cnt[x];
    }
    priority_queue<int> pq;
    for (auto& [_, v] : cnt) {
      pq.push(v);
    }
    int ans = nums.size();
    while (pq.size() > 1) {
      int x = pq.top();
      pq.pop();
      int y = pq.top();
      pq.pop();
      x--;
      y--;
      if (x > 0) {
        pq.push(x);
      }
      if (y > 0) {
        pq.push(y);
      }
      ans -= 2;
    }
    return ans;
  }
};

func minLengthAfterRemovals(nums []int) int {
  cnt := map[int]int{}
  for _, x := range nums {
    cnt[x]++
  }
  h := &hp{}
  for _, x := range cnt {
    h.push(x)
  }
  ans := len(nums)
  for h.Len() > 1 {
    x, y := h.pop(), h.pop()
    if x > 1 {
      h.push(x - 1)
    }
    if y > 1 {
      h.push(y - 1)
    }
    ans -= 2
  }
  return ans
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (h *hp) Push(v any)    { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}
func (h *hp) push(v int) { heap.Push(h, v) }
func (h *hp) pop() int   { return heap.Pop(h).(int) }

function minLengthAfterRemovals(nums: number[]): number {
  const cnt: Map<number, number> = new Map();
  for (const x of nums) {
    cnt.set(x, (cnt.get(x) ?? 0) + 1);
  }
  const pq = new MaxPriorityQueue();
  for (const [_, v] of cnt) {
    pq.enqueue(v);
  }
  let ans = nums.length;
  while (pq.size() > 1) {
    let x = pq.dequeue().element;
    let y = pq.dequeue().element;
    if (--x > 0) {
      pq.enqueue(x);
    }
    if (--y > 0) {
      pq.enqueue(y);
    }
    ans -= 2;
  }
  return ans;
}