2856. Minimum Array Length After Pair Removals LeetCode Solution

In this guide, you will get 2856. Minimum Array Length After Pair Removals LeetCode Solution with the best time and space complexity. The solution to Minimum Array Length After Pair Removals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Array Length After Pair Removals solution in C++
Minimum Array Length After Pair Removals solution in Java
Minimum Array Length After Pair Removals solution in Python
Additional Resources

2856. Minimum Array Length After Pair Removals LeetCode Solution image

Problem Statement of Minimum Array Length After Pair Removals

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 <= 105
1 <= nums[i] <= 109
nums is sorted in non-decreasing order.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2856. Minimum Array Length After Pair Removals LeetCode Solution in C++

class Solution {
 public:
  int minLengthAfterRemovals(vector<int>& nums) {
    const int n = nums.size();
    unordered_map<int, int> count;
    int maxFreq = 0;

    for (const int num : nums)
      ++count[num];

    for (const auto& [_, freq] : count)
      maxFreq = max(maxFreq, freq);

    // The number with the maximum frequency cancel all the other numbers.
    if (maxFreq <= n / 2)
      return n % 2;
    // The number with the maximum frequency cancel all the remaining numbers.
    return maxFreq - (n - maxFreq);
  }
};
/* code provided by PROGIEZ */

2856. Minimum Array Length After Pair Removals LeetCode Solution in Java

class Solution {
  public int minLengthAfterRemovals(List<Integer> nums) {
    final int n = nums.size();
    Map<Integer, Integer> count = new HashMap<>();
    int maxFreq = 0;

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    for (final int freq : count.values())
      maxFreq = Math.max(maxFreq, freq);

    // The number with the maximum frequency cancel all the other numbers.
    if (maxFreq <= n / 2)
      return n % 2;
    // The number with the maximum frequency cancel all the remaining numbers.
    return maxFreq - (n - maxFreq);
  }
}
// code provided by PROGIEZ

2856. Minimum Array Length After Pair Removals LeetCode Solution in Python

class Solution:
  def minLengthAfterRemovals(self, nums: list[int]) -> int:
    n = len(nums)
    count = collections.Counter(nums)
    maxFreq = max(count.values())

    # The number with the maximum frequency cancel all the other numbers.
    if maxFreq <= n / 2:
      return n % 2
    # The number with the maximum frequency cancel all the remaining numbers.
    return maxFreq - (n - maxFreq)
 # code by PROGIEZ