Amazon — Top K Frequent Elements (Bucket Sort or Heap)

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k is in the range [1, number of unique elements]
• Answer is guaranteed to be unique

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

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

Why This Problem Matters#

Top K Frequent Elements (LeetCode 347) is one of Amazon's most-asked medium problems, appearing in virtually every interview loop. It models Amazon's recommendation systems: "show the user their top-k most purchased categories," "surface the top-k trending search terms," or "rank the most-reviewed products." Understanding frequency-based ranking is a core skill for Amazon engineers.

Three approaches exist: sort by frequency (O(N log N)), a min-heap of size k (O(N log k)), and bucket sort (O(N)). The bucket sort approach is the most impressive: since frequencies range from 1 to N, you can create N+1 buckets indexed by frequency. Elements in the same bucket have the same frequency. Scan from the highest-frequency bucket downward to collect k elements.

The heap approach is more commonly expected in interviews because it is more general. Google, Meta, and Microsoft also ask this problem and expect the heap solution with the O(N log k) analysis.

The Core Insight#

Heap approach: Count frequencies with a hashmap. Maintain a min-heap of size k. For each (element, freq) pair, push to the heap. If the heap exceeds size k, pop the minimum-frequency element. The heap always contains the k most frequent elements.

Bucket sort approach: Create a list of N+1 empty buckets. Bucket i holds all elements with frequency i. Scan from bucket N down to bucket 1, collecting elements until you have k.

Both work. Bucket sort is O(N) but only beats heap for large N when k is also large.

Visual Dry Run#

nums = [1,1,1,2,2,3], k = 2

Frequency map: {1:3, 2:2, 3:1}

Bucket sort buckets (index = frequency):

• Bucket 1: [3]
• Bucket 2: [2]
• Bucket 3: [1]

Scan from bucket 3 down: take [1], then [2] → result = [1, 2]

Solution (Optimal)#

from collections import Counter
import heapq
 
class Solution:
    # Heap approach — O(N log k)
    def topKFrequent(self, nums: list, k: int) -> list:
        freq = Counter(nums)
        return heapq.nlargest(k, freq.keys(), key=freq.get)
 
    # Bucket sort approach — O(N)
    def topKFrequentBucket(self, nums: list, k: int) -> list:
        freq = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
 
        for num, count in freq.items():
            buckets[count].append(num)
 
        result = []
        for i in range(len(buckets) - 1, 0, -1):
            result.extend(buckets[i])
            if len(result) >= k:
                return result[:k]
 
        return result

// Heap approach (using sort as proxy for small inputs)
var topKFrequent = function(nums, k) {
    const freq = new Map();
    for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
 
    return [...freq.entries()]
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(([num]) => num);
};
 
// Bucket sort approach — O(N)
var topKFrequentBucket = function(nums, k) {
    const freq = new Map();
    for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
 
    const buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (const [num, count] of freq) buckets[count].push(num);
 
    const result = [];
    for (let i = buckets.length - 1; i >= 1 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
    return result.slice(0, k);
};

Time: O(N log k) with heap; O(N) with bucket sort Space: O(N) for frequency map; O(N) for buckets

Common Mistakes#

• Sorting all elements by frequency — O(N log N) is worse than the heap approach
• Using a max-heap and popping k times — works but less clean than nlargest
• Bucket sort with N buckets when frequencies exceed N — never happens (max freq is N)
• Off-by-one in bucket scan: starting at len(buckets) instead of len(buckets)-1
• Returning more than k elements from the bucket scan — must slice to k

Interview Tips#

• Start with the frequency count using a hashmap or Counter — both approaches start here
• Mention both heap O(N log k) and bucket sort O(N) approaches; implement whichever Amazon asks
• Python's heapq.nlargest(k, freq.keys(), key=freq.get) is one clean line — know it
• The bucket sort is impressive to show; explain that max frequency is bounded by N
• Amazon may ask you to sort by frequency then alphabetically for ties — add secondary sort key

Follow-up Questions#

• How would you sort by frequency then lexicographically for ties? — Add secondary key to sort
• What if k equals the number of unique elements? — Return all elements; any approach works
• What if the data is streaming? — Use a min-heap of size k with online frequency tracking
• How do you find the k least frequent elements? — Reverse the comparator or use a max-heap of size k
• What if elements can be strings instead of integers? — Same algorithm; hashmap and heap work for any hashable type

Key Takeaways#

• Frequency counting with a hashmap is the first step for both heap and bucket sort approaches
• A min-heap of size k gives the top-k frequent in O(N log k) — better than O(N log N) full sort
• Bucket sort achieves O(N) by exploiting that frequencies are bounded in [1, N]
• Python's heapq.nlargest(k, keys, key=freq.get) is the cleanest one-liner for heap approach
• Amazon tests this to verify frequency-ranking thinking applicable to real recommendation systems
• The bucket sort approach is the expected O(N) solution that impresses interviewers at Google and Amazon
• Both approaches use O(N) space; the bucket array size is always N+1 regardless of element values