# 2856. Minimum Array Length After Pair Removals

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,3,4,9]
</strong><strong>Output: 0
</strong><strong>Explanation: Initially, nums = [1, 3, 4, 9].
</strong>In the first operation, we can choose index 0 and 1 because nums[0] &#x3C; nums[1] &#x3C;=> 1 &#x3C; 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] &#x3C; nums[1] &#x3C;=> 4 &#x3C; 9.
Remove indices 0 and 1, and nums becomes an empty array [].
Hence, the minimum length achievable is 0.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [2,3,6,9]
</strong><strong>Output: 0
</strong><strong>Explanation: Initially, nums = [2, 3, 6, 9]. 
</strong>In the first operation, we can choose index 0 and 2 because nums[0] &#x3C; nums[2] &#x3C;=> 2 &#x3C; 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] &#x3C; nums[1] &#x3C;=> 3 &#x3C; 9. 
Remove indices 0 and 1, and nums becomes an empty array []. 
Hence, the minimum length achievable is 0.
</code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [1,1,2]
</strong><strong>Output: 1
</strong><strong>Explanation: Initially, nums = [1, 1, 2].
</strong>In an operation, we can choose index 0 and 2 because nums[0] &#x3C; nums[2] &#x3C;=> 1 &#x3C; 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. 
</code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

Remove the highest two frequencies at each time and Push in Heap and 
Continue this again and again
```

### Links

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

### Video Links

<https://www.youtube.com/watch?v=Qt_gbCWqFdY&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
typedef pair<int,int> PII;
class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        unordered_map<int,int> mp;
        for(auto &it: nums)
            mp[it]++;

        priority_queue<PII> pq;
        for(auto &it: mp)
            pq.push({it.second, it.first});

        while(pq.size() > 1){
            int num1 = pq.top().first;
            int val1 = pq.top().second;
            pq.pop();

            int num2 = pq.top().first;
            int val2 = pq.top().second;
            pq.pop();

            num1--; num2--;

            if(num1)
                pq.push({num1, val1});
            if(num2)
                pq.push({num2, val2});
        }

        int ans=0;
        if(!pq.empty()) 
            ans = pq.top().first;
        return ans;
    }
};

/*
    auto compare = [](const PII &a, const PII &b){
        return a.second < b.second;
    };
    priority_queue<PII, vector<PII>, decltype(compare)> pq(compare);
*/
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###