# Minimum Array Length After Pair Removals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-array-length-after-pair-removals)
Canonical: https://scaleengineer.com/dsa/problems/minimum-array-length-after-pair-removals
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-array-length-after-pair-removals/image0.gif)

**Example 2:**

**Input:** nums = \[1,1,2,2,3,3\]

**Output:** 0

**Explanation:**

![](https://assets.glich.co/dsa/minimum-array-length-after-pair-removals/image1.gif)

**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:**

![](https://assets.glich.co/dsa/minimum-array-length-after-pair-removals/image2.gif)

**Constraints:**

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

# Approaches
## Greedy Two-Pointer Approach
The core idea is that to maximize the number of removals, we should pair smaller elements with larger elements. Since the input array `nums` is sorted, this naturally suggests pairing elements from the first half of the array with elements from the second half. This greedy strategy can be implemented efficiently using a two-pointer technique.
**Time:** O(n), where n is the number of elements in the array. Both pointers `i` and `j` traverse their respective halves of the array at most once. · **Space:** O(1) extra space, as we only use a few variables for the pointers and the count.
**Pros:** Achieves optimal time and space complexity.; The logic is a direct and intuitive simulation of an effective pairing strategy.; Works correctly for both even and odd length arrays due to the `(n+1)/2` split point.
**Cons:** The optimality of this specific greedy strategy (pairing the first half with the second half) might not be immediately obvious without some reasoning.
### Explanation
We use two pointers, `i` and `j`, to traverse the first and second halves of the array, respectively. The pointer `i` starts at the beginning of the array (`0`), and `j` starts at the beginning of the second half (at index `(n + 1) / 2` to handle both even and odd length arrays correctly). We iterate through the array and try to form pairs. If `nums[i]` is smaller than `nums[j]`, we have a valid pair. We count this pair and advance both pointers to look for the next pair. If `nums[i]` is not smaller than `nums[j]`, we can't pair them. Since `nums[i]` is fixed, we need to find a larger element in the second half, so we advance `j` while keeping `i` the same. The process continues until one of the pointers goes out of its respective half's bounds. The final answer is the initial length minus twice the number of pairs found.

```java
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }

        int i = 0;
        int j = (n + 1) / 2;
        int pairs = 0;

        while (i < n / 2 && j < n) {
            if (nums.get(i) < nums.get(j)) {
                pairs++;
                i++;
                j++;
            } else {
                j++;
            }
        }

        return n - 2 * pairs;
    }
}
```
### Algorithm
- Initialize two pointers, `i` starting at `0` and `j` starting at `(n + 1) / 2`, where `n` is the length of the array.
- Initialize a counter `pairs` to `0`.
- Loop while `i` is in the first half (i.e., `i < (n + 1) / 2`) and `j` is in the second half (i.e., `j < n`):
  - If `nums[i] < nums[j]`, it means we can form a pair. Increment `pairs`, and advance both pointers `i` and `j`.
  - Otherwise (`nums[i] >= nums[j]`), we cannot pair `nums[i]` with `nums[j]`. We need to find a larger element in the second half for `nums[i]`, so we only advance `j`.
- After the loop terminates, the total number of elements removed is `2 * pairs`.
- The minimum length of the remaining array is `n - 2 * pairs`.

## Frequency Counting Approach
This approach analyzes the problem from a frequency perspective. The minimum length of the final array is determined by a single factor: the frequency of the most common element. If one element is very frequent, it becomes a bottleneck for pairing. Otherwise, if the frequencies are more balanced, we can pair up almost all elements.
**Time:** O(n), as finding the maximum frequency requires a single pass through the sorted array. · **Space:** O(1) extra space. We only need a few variables to track frequencies, not a full frequency map, because the array is sorted.
**Pros:** Optimal O(n) time and O(1) space complexity.; The implementation is very concise and efficient, potentially having better constant factors than the two-pointer approach due to simpler logic.; Provides a deeper, mathematical understanding of the problem's constraints.
**Cons:** The mathematical reasoning behind the two cases might be less intuitive to derive compared to a direct simulation approach.
### Explanation
Let `n` be the length of the array. The key insight is to consider the frequency of the most frequent element, let's call it `max_freq`. 

Case 1: `max_freq > n / 2`. The most frequent element is a majority. We have `max_freq` copies of this number and `n - max_freq` other numbers. We can make at most `n - max_freq` pairs by pairing each of the 'other' numbers with one instance of the most frequent number. This leaves `max_freq - (n - max_freq) = 2 * max_freq - n` instances of the most frequent number, which cannot be paired among themselves. This is the minimum remaining length.

Case 2: `max_freq <= n / 2`. No element has a majority. This means there's a sufficient variety of other numbers to pair with the instances of the most frequent element. In this scenario, we can pair up almost everything. If `n` is even, we can form `n/2` pairs and leave 0 elements. If `n` is odd, one element will be left over. So, the result is `n % 2`.

Since the input array is sorted, finding `max_freq` is a simple O(n) pass.

```java
class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        if (n <= 1) {
            return n;
        }

        int max_freq = 0;
        int current_freq = 1;
        for (int i = 1; i < n; i++) {
            if (nums.get(i).equals(nums.get(i - 1))) {
                current_freq++;
            } else {
                max_freq = Math.max(max_freq, current_freq);
                current_freq = 1;
            }
        }
        max_freq = Math.max(max_freq, current_freq);

        if (max_freq > n / 2) {
            return 2 * max_freq - n;
        } else {
            return n % 2;
        }
    }
}
```
### Algorithm
- Calculate the total number of elements, `n`.
- Find the frequency of the most common element in the array, `max_freq`. Since the array is sorted, this can be done in a single pass by counting consecutive identical elements.
- Compare `max_freq` with `n / 2`:
  - If `max_freq > n / 2`, the most frequent element is the bottleneck. The number of remaining elements will be `2 * max_freq - n`.
  - If `max_freq <= n / 2`, no single element is a bottleneck. We can pair up almost all elements. The number of remaining elements will be `n % 2` (0 if `n` is even, 1 if `n` is odd).
- Return the calculated result.

# Solutions
### Java

```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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```