Skip to content

1338. Reduce Array Size to The Half 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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((a, b) -> b.getValue().compareTo(a.getValue()));

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

    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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