1338. Reduce Array Size to The Half LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1338. Reduce Array Size to The Half LeetCode Solution with the best time and space complexity. The solution to Reduce Array Size to The Half 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
Reduce Array Size to The Half solution in C++
Reduce Array Size to The Half solution in Java
Reduce Array Size to The Half solution in Python
Additional Resources

1338. Reduce Array Size to The Half LeetCode Solution image

Problem Statement of Reduce Array Size to The Half

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Example 2:

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Constraints:

2 <= arr.length <= 105
arr.length is even.
1 <= arr[i] <= 105

Complexity Analysis

Time Complexity:
Space Complexity:

1338. Reduce Array Size to The Half LeetCode Solution in C++

class Solution {
 public:
  int minSetSize(vector<int>& arr) {
    const int n = arr.size();
    int sum = 0;
    unordered_map<int, int> count;
    vector<pair<int, int>> numAndFreqs;

    for (const int a : arr)
      ++count[a];

    for (const auto& [a, freq] : count)
      numAndFreqs.emplace_back(a, freq);

    ranges::sort(
        numAndFreqs, ranges::greater{},
        [](const pair<int, int>& numAndFreq) { return numAndFreq.second; });

    for (int i = 0; i < numAndFreqs.size(); ++i) {
      sum += numAndFreqs[i].second;
      if (sum >= n / 2)
        return i + 1;
    }

    throw;
  }
};
/* code provided by PROGIEZ */

1338. Reduce Array Size to The Half LeetCode Solution in Java

class Solution {
  public int minSetSize(int[] arr) {
    final int n = arr.length;
    int sum = 0;
    Map<Integer, Integer> count = new HashMap<>();
    List<Map.Entry<Integer, Integer>> numAndFreqs = new ArrayList<>();

    for (final int a : arr)
      count.merge(a, 1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet())
      numAndFreqs.add(entry);

    numAndFreqs.sort(Comparator.comparing(Map.Entry<Integer, Integer>::getValue).reversed());

    for (int i = 0; i < numAndFreqs.size(); ++i) {
      sum += numAndFreqs.get(i).getValue();
      if (sum >= n / 2)
        return i + 1;
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

1338. Reduce Array Size to The Half LeetCode Solution in Python

class Solution:
  def minSetSize(self, arr: list[int]) -> int:
    count = collections.Counter(arr).most_common()
    count.sort(key=lambda x: -x[1])

    summ = 0
    for i, (_, freq) in enumerate(count):
      summ += freq
      if summ >= len(arr) // 2:
        return i + 1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents