Sort the frequencies in ascending order.
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.
Return the minimum number of elements needed to reach at least half the array size.
Code

[{"language":"Java","code":"class Solution {\n\tpublic int minSetSize(int[] arr) {\n\t\tMap<Integer, Integer> freqMap = new HashMap<>();\n\t\tfor (int num : arr) {\n\t\t\tfreqMap.put(num, freqMap.getOrDefault(num, 0) + 1);\n\t\t}\n\t\n\t\tint[] frequencies = new int[freqMap.values().size()];\n\t\tint i = 0;\n\t\tfor (int freq : freqMap.values()) {\n\t\t\tfrequencies[i++] = freq;\n\t\t}\n\t\tArrays.sort(frequencies);\n\t\n\t\tfinal int HALF = arr.length / 2;\n\t\tint ans = 0, removed = 0;\n\t\ti = frequencies.length - 1;\n\t\twhile (removed < HALF) {\n\t\t\tans += 1;\n\t\t\tremoved += frequencies[i--];\n\t\t}\n\t\treturn ans;\n\t}\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tpublic</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minSetSize</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">arr</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">\t\tMap&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Integer</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">Integer</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> freqMap </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> new</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> HashMap&#x3C;>();</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\tfor</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> num </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">:</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> arr) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">\t\t\tfreqMap.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">put</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(num, freqMap.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">getOrDefault</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(num, </span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">+</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">);</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">\t\t}
Related Tags
