Top K frequent Elements

XXX. Top K Frequent Elements

Hash Map

Heap

Bucket Sort

Problem Statement:

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

Approach 1: Min-Heap

1. Use a hash map to store the frequency of each element in the array.
2. Maintain a min-heap (priority queue) to track the top k elements with the highest frequency.
3. Iterate through the frequency map, adding elements to the heap and ensuring its size does not exceed k.
4. Extract the elements from the heap to form the result array.

Approach 2: Bucket Sort

1. Use a hash map to calculate the frequency of each element.
2. Create a bucket array where the index represents the frequency of elements.
3. Iterate through the frequency map and place each element in the corresponding bucket based on its frequency.
4. Traverse the bucket array in reverse order to collect the top k frequent elements.

Algorithm Intuition:

The problem can be efficiently solved using either:

• A **min-heap**, which maintains the top k elements in terms of frequency. This approach ensures we only store a fixed number of elements, minimizing memory usage.
• A **bucket sort** strategy, which groups elements by their frequency. By traversing the bucket in reverse order, we can directly retrieve the most frequent elements without additional sorting.

Both methods use a hash map to count frequencies as the first step, ensuring that the algorithm is efficient.

Complexity:

Heap-Based Approach:
Time Complexity: O(N log k), where N is the number of elements in the array. Each insertion/removal in the heap takes O(log k).
Space Complexity: O(N + k), for the frequency map and the heap.

Bucket Sort Approach:
Time Complexity: O(N), as it involves one pass to count frequencies and one pass through the bucket array.
Space Complexity: O(N), for the frequency map and the bucket array.

Java Implementation:

// Easy but make sure to insert numbers in freq map BEFORE starting to add to heap
public int[] topKFrequent(int[] nums, int k) {
    Map freq = new HashMap<>();
    PriorityQueue q = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
    int[] res = new int[k];

    // Step 1: Build frequency map
    for (int num : nums) 
        freq.put(num, freq.getOrDefault(num, 0) + 1);

    // Step 2: Maintain a min-heap for top K frequent elements
    for (int num : freq.keySet()) {
        q.offer(num);
        while (q.size() > k) 
            q.poll(); // Remove the least frequent element
    }

    // Step 3: Extract elements from heap
    int i = 0;
    while (!q.isEmpty()) 
        res[i++] = q.poll();

    return res;
}

// Even better solution using bucket sort
public List topKFrequentBucket(int[] nums, int k) {
    // Step 1: Initialize bucket array and frequency map
    List[] bucket = new List[nums.length + 1];
    for (int i = 0; i < bucket.length; i++) 
        bucket[i] = new ArrayList<>();
        
    Map frequencyMap = new HashMap<>();

    // Step 2: Count frequencies
    for (int n : nums) 
        frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);

    // Step 3: Place elements into corresponding frequency buckets
    for (int key : frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        bucket[frequency].add(key);
    }

    // Step 4: Collect top K frequent elements from the buckets
    List res = new ArrayList<>();
    for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
        if (bucket[pos] != null) 
            res.addAll(bucket[pos]);
    }

    return res;
}