Top K Frequent Elements

1package pkg5leetcode.blind75;2 3/*4 * Top K Frequent Elements | LC 3475 * APPROACH: Count frequencies; min-heap of size k by frequency.6 * COMPLEXITY: Time O(n log k), Space O(n)7 */8import java.util.*;9 10public class blind75_LC347TopKFrequentElements {11    static int[] topKFrequent(int[] nums, int k) {12        Map<Integer, Integer> freq = new HashMap<>();13        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);14        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));15        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {16            pq.offer(new int[]{e.getKey(), e.getValue()});17            if (pq.size() > k) pq.poll();18        }19        int[] res = new int[k];20        for (int i = k - 1; i >= 0; i--) res[i] = pq.poll()[0];21        return res;22    }23 24    public static void main(String[] args) {25        int[] r = topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);26        Arrays.sort(r);27        check(Arrays.equals(r, new int[]{1, 2}), "case1");28        check(topKFrequent(new int[]{1}, 1)[0] == 1, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}