Back to Arrays & Hashing
Medium
Top K Frequent Elements
Given an integer array `nums` and an integer `k`, return the `k` most frequent elements. You may return the answer in any order.
Examples
Input:nums = [1,1,1,2,2,3], k = 2
Output:[1,2]
1 occurs three times and 2 occurs twice, making them the top 2 frequent elements.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4k is in the range [1, the number of unique elements in the array].It is guaranteed that the answer is unique.
Approach
First, count the frequencies of each element using a hash map. Then, use a Min Heap of size k to keep track of the top k elements. Iterate through the hash map, adding elements to the heap. If the heap size exceeds k, pop the smallest element. After iterating, the heap will contain the top k frequent elements.
Complexity Analysis
Time Complexity
O(n log k)
Space Complexity
O(n + k)
O(n) time to build the hash map, and O(n log k) to insert elements into the heap.
Solution.java
class Solution { public int[] topKFrequent(int[] nums, int k) { // Count frequencies Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } // Priority queue (Min Heap) ordered by frequency PriorityQueue<Integer> heap = new PriorityQueue<>( (n1, n2) -> count.get(n1) - count.get(n2) ); // Keep k top frequent elements in the heap for (int n : count.keySet()) { heap.add(n); if (heap.size() > k) { heap.poll(); } } // Extract elements from heap int[] top = new int[k]; for (int i = k - 1; i >= 0; --i) { top[i] = heap.poll(); } return top; }}