How to Explain Top K Frequent Elements in a Coding Interview (Step-by-Step)

Top K Frequent Elements is a problem where knowing three different solutions and their tradeoffs separates average candidates from strong ones. Most people know the heap approach — but the bucket sort solution is O(n) and interviewers love it.

In this post, you’ll learn exactly how to walk an interviewer through all three approaches, when to use each, and which edge cases to call out proactively.

Problem Statement

Examples

Constraints

• 1 <= nums.length <= 10⁵
• k is in the range [1, the number of unique elements]
• The answer is guaranteed to be unique
• Your algorithm must be better than O(n log n)

What Is the Problem?

“I need to count how often each number appears in the array, then return the top k numbers by frequency. The order of the output doesn’t matter.”

Note the constraint — the problem explicitly asks for better than O(n log n). This is a hint to push toward O(n).

Step 1: Walk Through All Three Approaches

This is a problem where showing the progression from naive to optimal earns maximum points:

Step 2: Explain the Bucket Sort Approach in Plain English

“First I count frequencies with a HashMap. Then I create a list of n + 1 empty buckets — index represents frequency. I place each number into its frequency bucket. Finally I scan the buckets from right to left, collecting elements until I have k.”

Approach 1 — Min-Heap (mention first, good to know)

import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)         # Step 1: count frequencies

        # Step 2: use a min-heap of size k
        # heapq.nlargest picks top k by frequency in O(n log k)
        return heapq.nlargest(k, count.keys(), key=lambda x: count[x])

“The heap approach is O(n log k) — better than sorting since k ≤ n. But we can do even better with bucket sort.”

Approach 2 — Bucket Sort (optimal, lead with this)

from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)              # Step 1: count frequencies
        buckets = [[] for _ in range(len(nums) + 1)]  # Step 2: index = frequency

        for num, freq in count.items():
            buckets[freq].append(num)      # Step 3: place num in its freq bucket

        result = []
        for i in range(len(buckets) - 1, 0, -1):  # Step 4: scan right to left
            for num in buckets[i]:
                result.append(num)
                if len(result) == k:       # Stop as soon as we have k elements
                    return result

Visual Walkthrough

Tracing through nums = [1, 1, 1, 2, 2, 3], k = 2:

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

Let n = length of nums.

“The bucket sort approach is O(n) — we do a single pass to count, a single pass to fill buckets, and at most one full pass to collect results. It satisfies the problem’s constraint of being better than O(n log n).”

Interview Checklist for Top K Frequent Elements

• Restate — “return the k elements with the highest frequency”
• Notice and call out the O(n log n) constraint in the problem
• Present all three approaches — sort, heap, bucket sort
• State the core bucket sort insight — max frequency is n, so buckets are bounded
• Explain the right-to-left scan to collect top k
• Handle multiple elements in the same bucket edge case
• State O(n log k) for heap and O(n) for bucket sort
• Explain why bucket sort satisfies the constraint — heap does too, but bucket is optimal
• Ask before coding, don’t just dive in

Related Problems to Practice

If you can solve Top K Frequent Elements cleanly, try these next: