Description
Given an integer array num sorted in non-decreasing order.
You can perform the following operation any number of times:
- Choose two indices,
i and j, where 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 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] <= 109nums 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 × log n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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) }(code-box)
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<number>();
for (const [_, v] of cnt) {
pq.enqueue(v);
}
let ans = nums.length;
while (pq.size() > 1) {
let x = pq.dequeue();
let y = pq.dequeue();
if (--x > 0) {
pq.enqueue(x);
}
if (--y > 0) {
pq.enqueue(y);
}
ans -= 2;
}
return ans;
}(code-box)
