2856. Minimum Array Length After Pair Removals
Description
Given an integer array num sorted in non-decreasing order.
You can perform the following operation any number of times:
- Choose two indices,
iandj, wherenums[i] < nums[j]. - Then, remove the elements at indices
iandjfromnums. The remaining elements retain their original order, and the array is re-indexed.
Return the minimum length of nums after applying the operation zero or more times.
Example 1:
Input: nums = [1,2,3,4]
Output: 0
Explanation:
Example 2:
Input: nums = [1,1,2,2,3,3]
Output: 0
Explanation:
Example 3:
Input: nums = [1000000000,1000000000]
Output: 2
Explanation:
Since both numbers are equal, they cannot be removed.
Example 4:
Input: nums = [2,3,4,4,4]
Output: 1
Explanation:
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109numsis 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$.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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) }
TypeScript
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;
}