347. Top K Frequent Elements

Array
Hash Table
Bucket Sort

TIME

O(n)

SPACE

O(n)

Intuition

Use bucket sort where index = frequency. Since max frequency is n, we create n+1 buckets. Elements with same frequency go in same bucket. Iterate buckets from high to low frequency to get top k.

Solution

Count frequencies: Use hash map to count occurrences of each number.
Create frequency buckets: Array of lists where buckets[f] contains all numbers with frequency f. Max frequency is n, so we need n+1 buckets.
Collect top k: Iterate from highest frequency bucket down, collect elements until we have k elements.

Why Bucket Sort?

Heap approach: O(n log k), good but not optimal
Sorting: O(n log n), doesn't meet follow-up requirement
Bucket sort: O(n), optimal, meets follow-up

Complexity

Time: O(n), one pass to count, one pass to bucket, one pass to collect
Space: O(n), frequency map and buckets

Edge Cases

Single element → return that element
All elements same frequency → any k of them is valid
k equals number of unique elements → return all unique elements

Code

from typing import List
from collections import defaultdict


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        347. Top K Frequent Elements
        Time: O(n)
        Space: O(n)
        """
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1

        buckets = [[] for _ in range(len(nums) + 1)]
        for num, f in freq.items():
            buckets[f].append(num)

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

        return res

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 347. Top K Frequent Elements
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        for (int i = 0; i <= nums.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            buckets[entry.getValue()].add(entry.getKey());
        }

        int[] res = new int[k];
        int idx = 0;

        for (int i = nums.length; i >= 0 && idx < k; i--) {
            for (int num : buckets[i]) {
                res[idx++] = num;
                if (idx == k) break;
            }
        }

        return res;
    }
}