Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3

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.

Solution

Method 1 - Create Array on Frequency Map of Array Elements

Approach

  1. Count the frequency of each element in the array using a hash map.
  2. Store all frequencies in an array.
  3. Sort the frequencies in ascending order.
  4. Starting from the largest frequency, keep removing elements (i.e., add frequencies to a running total) until at least half of the array is removed.
  5. Return the minimum number of elements needed to reach at least half the array size.

Code

 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) {
		Map<Integer, Integer> freqMap = new HashMap<>();
		for (int num : arr) {
			freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
		}
	
		int[] frequencies = new int[freqMap.values().size()];
		int i = 0;
		for (int freq : freqMap.values()) {
			frequencies[i++] = freq;
		}
		Arrays.sort(frequencies);
	
		final int HALF = arr.length / 2;
		int ans = 0, removed = 0;
		i = frequencies.length - 1;
		while (removed < HALF) {
			ans += 1;
			removed += frequencies[i--];
		}
		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • O(n) to build the frequency map
    • O(n) to build the frequencies array
    • O(n log n) to sort the frequencies
    • O(n) to accumulate removals
  • 🧺 Space complexity: O(n)
    • For the frequency map and the frequencies array

Method 2 - Frequency Map and Bucket Sort 🏆

Approach

  1. Count the frequency of each element in the array using a hash map.
  2. Use a counting array (bucket) to count how many numbers have each possible frequency.
  3. Start from the highest frequency and keep removing elements (adding frequencies to a running total) until at least half of the array is removed.
  4. Return the minimum number of elements needed to reach at least half the array size.

Code

 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

class Solution {
	public int minSetSize(int[] arr) {
		int n = arr.length;
		HashMap<Integer, Integer> cnt = new HashMap<>();
		for (int x: arr) {
			cnt.put(x, cnt.getOrDefault(x, 0) + 1);
		}
		// this array is already sorted
		// as highest freq is at end
		int[] counting = new int[n + 1];
		for (int freq: cnt.values()) {
			++counting[freq];
		}
	
		int ans = 0, removed = 0, half = n / 2, freq = n;
		while (removed<half) {
			ans += 1;
			while (counting[freq] == 0) {
				--freq;
			}
			removed += freq;
			--counting[freq];
		}
		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
    • O(n) to build the frequency map
    • O(n) to build the counting array
    • O(n) to accumulate removals (since the sum of all frequencies is n)
  • 🧺 Space complexity: O(n)
    • For the frequency map and the counting array

Method 3 - Use Max Heap on Frequency Map of Array Elements

Approach

  1. Count the frequency of each element in the array using a hash map.
  2. Add all frequencies to a max heap (priority queue).
  3. Repeatedly remove the largest frequency from the heap, adding it to a running total, until at least half of the array is removed.
  4. Return the minimum number of elements needed to reach at least half the array size.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
	public int minSetSize(int[] a) {
		Map<Integer, Integer> m = new HashMap<>();
		for (int n: a) {
			m.put(n, m.getOrDefault(n, 0) + 1);
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>((c, d) -> d - c);
		for (int n: m.keySet()) {
			pq.offer(m.get(n));
		}
		int res = 0, sum = 0;
		while (!pq.isEmpty()) {
			sum += pq.poll();
			res++;
			if (sum >= (a.length + 1) / 2) {
				return res;
			}
		}
		return 0;
	}
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • O(n) to build the frequency map
    • O(n) to add all frequencies to the max heap
    • Each heap operation is O(log n), and in the worst case, we may remove up to n/2 elements, so total heap operations are O(n log n).
  • 🧺 Space complexity: O(n)
    • For the frequency map and the max heap