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.

Algorithm:

Use a frequency map to count occurrences of each number in the array.
Depending on the solution, either use a priority queue (min-heap) or bucket sort:
- Heap-based solution: Insert elements into a min-heap of size k. If the heap exceeds size k, remove the smallest frequency element.
- Bucket sort solution: Use an array of lists where the index represents frequency, and collect the top k frequent elements by iterating from the highest frequency bucket downwards.

Complexity:

Heap-based solution:
Time Complexity: O(n log k), where n is the number of elements in nums.
Space Complexity: O(n + k), for the frequency map and heap.

Bucket sort solution:
Time Complexity: O(n), since we process the frequency map and iterate through the buckets.
Space Complexity: O(n), for the frequency map and buckets.

Java Implementation:

                
class Solution {

    // Solution using a min-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];

        // Count frequencies
        for (int num : nums) 
            freq.put(num, freq.getOrDefault(num, 0) + 1);

        // Add to heap and maintain size k
        for (int num : freq.keySet()) {
            q.offer(num);
            while (q.size() > k) 
                q.poll();
        }

        // Extract results from the heap
        int i = 0;
        while (!q.isEmpty()) 
            res[i++] = q.poll();

        return res;
    }

    // Solution using bucket sort
    public List topKFrequentBucket(int[] nums, int k) {
        List[] bucket = new List[nums.length + 1];
        for (int i = 0; i < bucket.length; i++) 
            bucket[i] = new ArrayList<>();

        Map frequencyMap = new HashMap<>();

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

        // Add numbers to corresponding frequency bucket
        for (int key : frequencyMap.keySet()) 
            bucket[frequencyMap.get(key)].add(key);

        List res = new ArrayList<>();

        // Collect results starting from the highest frequency
        for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) 
            if (bucket[pos] != null) 
                res.addAll(bucket[pos]);

        return res;
    }
}
                
            

Python Implementation:

                
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)
    return [item for item, _ in heapq.nlargest(k, freq.items(), key=lambda x: x[1])]

def top_k_frequent_bucket(nums, k):
    freq = Counter(nums)
    bucket = [[] for _ in range(len(nums) + 1)]

    for num, count in freq.items():
        bucket[count].append(num)

    res = []
    for i in range(len(bucket) - 1, -1, -1):
        for num in bucket[i]:
            res.append(num)
            if len(res) == k:
                return res
                
            

C++ Implementation:

                
#include 
#include 
#include 
#include 
using namespace std;

vector topKFrequent(vector& nums, int k) {
    unordered_map freq;
    for (int num : nums)
        freq[num]++;

    auto comp = [&](int a, int b) { return freq[a] > freq[b]; };
    priority_queue, decltype(comp)> minHeap(comp);

    for (auto& [num, count] : freq) {
        minHeap.push(num);
        if (minHeap.size() > k) 
            minHeap.pop();
    }

    vector res;
    while (!minHeap.empty()) {
        res.push_back(minHeap.top());
        minHeap.pop();
    }

    return res;
}

vector topKFrequentBucket(vector& nums, int k) {
    unordered_map freq;
    for (int num : nums)
        freq[num]++;

    vector> bucket(nums.size() + 1);
    for (auto& [num, count] : freq)
        bucket[count].push_back(num);

    vector res;
    for (int i = bucket.size() - 1; i >= 0 && res.size() < k; i--) 
        for (int num : bucket[i]) {
            res.push_back(num);
            if (res.size() == k)
                return res;
        }

    return res;
}
                
            

XXX. Top K Frequent Elements