Minimum Array Length After Pair Removals
MedPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize two pointers,
istarting at0andjstarting at(n + 1) / 2, wherenis the length of the array. - Initialize a counter
pairsto0. - Loop while
iis in the first half (i.e.,i < (n + 1) / 2) andjis in the second half (i.e.,j < n):- If
nums[i] < nums[j], it means we can form a pair. Incrementpairs, and advance both pointersiandj. - Otherwise (
nums[i] >= nums[j]), we cannot pairnums[i]withnums[j]. We need to find a larger element in the second half fornums[i], so we only advancej.
- If
- After the loop terminates, the total number of elements removed is
2 * pairs. - The minimum length of the remaining array is
n - 2 * pairs.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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)/2split 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.
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.
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_freqwithn / 2:- If
max_freq > n / 2, the most frequent element is the bottleneck. The number of remaining elements will be2 * 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 ben % 2(0 ifnis even, 1 ifnis odd).
- If
- Return the calculated result.
Walkthrough
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.
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; } }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.