Problem 7 - Top k frequent elements

Explore our archive for previous posts.

Question

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

• k is in the range [1, the number of unique elements in the array].

• It is guaranteed that the answer is unique.

Approach

This approach utilizes the concept of a min-heap to maintain the K most frequent elements efficiently. By using a min-heap, we always keep track of the smallest frequency element at the root, allowing us to replace it with a higher frequency element if necessary.

Here are the detailed steps:

1. Create a frequency map: Iterate through the given array and count the frequency of each element. Store this information in a frequency map, where the keys represent the elements, and the values represent their frequencies.

2. Build a heap: Initialize an empty min-heap. Iterate through the frequency map and insert each element-frequency pair into the heap. Since it is a min-heap, the element with the lowest frequency will be at the root.

3. Maintain the heap size: While inserting elements into the heap, if the size exceeds K, remove the element with the lowest frequency (root of the min-heap). This ensures that the heap always contains the K most frequent elements.

4. Extract the top K elements: After processing all the elements in the frequency map, the min-heap will contain the K most frequent elements. Extract these elements from the heap in descending order of frequency. To do this, perform K extract-min operations on the heap, each time adding the extracted element to the result list.

5. Return the result: Return the list of K most frequent elements obtained in the previous step.

Solution

Solve it here

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Count the frequency of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        // Create a min heap to store the top K frequent elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
        
        // Iterate over the numbers and maintain the size of the heap to be K
        for (int num : freqMap.keySet()) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        // Convert the heap to an array
        int[] result = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll();
        }
        
        return result;
    }
}

Time and space complexity

Time Complexity: The time complexity of this approach is O(N log K), where N is the number of elements in the array. Constructing the frequency map takes O(N) time, and inserting and extracting elements from the min-heap take O(log K) time each. Since we perform these operations N times, the overall time complexity is O(N log K).

Space Complexity: The space complexity is O(N) to store the frequency map and O(K) for the min-heap, resulting in a total space complexity of O(N + K). One could also approximate it to O(N) since K is usually much smaller than N.