Top K Frequent Elements

Top K Frequent Elements looks easy at first. Just count and pick the top ones, right? But the interviewer wants to see how you pick the top ones without sorting everything. That choice is the whole point of this question.

🎯 The Problem

You get an array of numbers and a number k, and return the most common numbers.

• Return the k numbers that show up the most times.
• The frequency of a number is how many times it appears.
• A number that appears often belongs in the answer.
• Assume the answer is always clear, so there is one correct set.

Let us say the array is [1, 1, 1, 2, 2, 3] and k is 2. The number 1 appears three times. The number 2 appears two times. The number 3 appears once. So the two most frequent numbers are 1 and 2.

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

Explanation: 1 appears 3 times, 2 appears 2 times, 3 appears 1 time.
The top 2 by frequency are 1 and 2.

Here is the frequency picture of our example. Each number points to how many times it appears.

🐢 Approach 1: Count Then Sort (Brute Force)

The idea in one line: count every number, then sort by count and take the first k.

The idea:

• A hash map stores a key and a value and looks the key up almost instantly.
• Build a map of each number to its count.
• Sort all the numbers by count, high to low.
• Take the first k.

Why it is weak:

• Sorting orders every unique number, even the rare ones you discard.
• That costs O(n log n), where n is how many unique numbers there are.
• You only need the top k, not a full order.

Here is the count-then-sort code:

from collections import Counter


def top_k_frequent(nums, k):
    counts = Counter(nums)
    ordered = sorted(counts, key=lambda num: counts[num], reverse=True)
    return ordered[:k]

⚖️ Approach 2: Count Then Heap of Size k (Better)

The idea in one line: keep only the k strongest counts in a heap, dropping the smallest as you go.

The idea:

• A heap always keeps the smallest or largest item ready at the top.
• Keep a heap of size k.

How it works:

• Walk each number and its count.
• Push it into the heap.
• If the heap grows past k, remove the smallest.
• At the end the heap holds the k highest counts.

Why it is better:

• Each push or pop on a heap of size k costs O(log k).
• The total is about O(n log k).
• That beats O(n log n) when k is smaller than n.

Here is the heap-of-size-k code:

from collections import Counter
import heapq


def top_k_frequent(nums, k):
    heap = []
    for num, freq in Counter(nums).items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for freq, num in heap]

⚡ Approach 3: Count Then Bucket Sort (Best)

The idea in one line: use the count itself as an index, so you read the top numbers in order with no sorting.

The idea:

• A number can appear at most n times, where n is the array length.
• So every count sits between 1 and n.
• A bucket is a slot that holds all numbers sharing one count.

How it works:

• Make empty buckets, one for each count from 0 to n.
• Put each number into the bucket that matches its count.
• Walk the buckets from the highest count down.
• Collect numbers until you have k.

Why it is fast:

• Count in one pass. Fill buckets in one pass. Read back in one pass.
• No sorting at all. So the time is O(n).
• That is as fast as it gets, since you must see every number once.

Here is the bucket layout for our example. Index is the count. The slot holds the numbers with that count.

Steps to Solve

1. Walk through the array and build a hash map of each number to its count.
2. Make a list of empty buckets, one slot for each count from 0 up to the array length.
3. For each number, put it in the bucket whose index equals its count.
4. Walk the buckets from the highest index down to the lowest.
5. Collect numbers from each bucket until you have gathered k of them.
6. Return those k numbers.

#include <stdio.h>

int main(void) {
    int nums[] = {1, 1, 1, 2, 2, 3};
    int n = 6;
    int k = 2;

    // counts indexed by the number itself (values here are small)
    int count[10] = {0};
    for (int i = 0; i < n; i++) {
        count[nums[i]]++;        // add one to this number's count
    }

    // buckets[c] will mark which numbers have count c
    // walk counts from high (n) down to low and collect k numbers
    int result[10];
    int found = 0;
    for (int c = n; c >= 1 && found < k; c--) {
        for (int num = 0; num < 10; num++) {
            if (count[num] == c) {       // this number has count c
                result[found++] = num;
                if (found == k) break;
            }
        }
    }

    printf("[");
    for (int i = 0; i < found; i++) {
        printf("%d", result[i]);
        if (i < found - 1) printf(", ");
    }
    printf("]\n");
    return 0;
}

[1, 2]

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;       // number -> how many times
    for (int num : nums) count[num]++;

    int n = nums.size();
    vector<vector<int>> buckets(n + 1);  // buckets[freq] holds numbers
    for (auto& pair : count) {
        buckets[pair.second].push_back(pair.first);
    }

    vector<int> result;
    for (int freq = n; freq >= 1 && (int)result.size() < k; freq--) {
        for (int num : buckets[freq]) {
            result.push_back(num);
            if ((int)result.size() == k) break;
        }
    }
    return result;
}

int main() {
    vector<int> nums = {1, 1, 1, 2, 2, 3};
    int k = 2;
    vector<int> result = topKFrequent(nums, k);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[1, 2]

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

public class TopKFrequent {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();   // number -> count
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        int n = nums.length;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= n; i++) buckets.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            buckets.get(e.getValue()).add(e.getKey());   // place by frequency
        }

        List<Integer> result = new ArrayList<>();
        for (int freq = n; freq >= 1 && result.size() < k; freq--) {
            for (int num : buckets.get(freq)) {
                result.add(num);
                if (result.size() == k) break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 1, 1, 2, 2, 3 };
        int k = 2;
        System.out.println(topKFrequent(nums, k));
    }
}

[1, 2]

def top_k_frequent(nums, k):
    count = {}                          # number -> how many times
    for num in nums:
        count[num] = count.get(num, 0) + 1

    n = len(nums)
    buckets = [[] for _ in range(n + 1)]  # buckets[freq] holds numbers
    for num, freq in count.items():
        buckets[freq].append(num)         # place number by its frequency

    result = []
    for freq in range(n, 0, -1):          # walk from highest count down
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result


nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent(nums, k))

[1, 2]

function topKFrequent(nums, k) {
  const count = new Map(); // number -> how many times
  for (const num of nums) {
    count.set(num, (count.get(num) || 0) + 1);
  }

  const n = nums.length;
  const buckets = Array.from({ length: n + 1 }, () => []); // by frequency
  for (const [num, freq] of count) {
    buckets[freq].push(num);
  }

  const result = [];
  for (let freq = n; freq >= 1 && result.length < k; freq--) {
    for (const num of buckets[freq]) {
      result.push(num);
      if (result.length === k) break;
    }
  }
  return result;
}

const nums = [1, 1, 1, 2, 2, 3];
const k = 2;
console.log(topKFrequent(nums, k));

[ 1, 2 ]

Let us walk through the Python version line by line, so you see why each part is there.

The line count = {} makes an empty dictionary. This will hold each number and how many times it shows up.

The loop for num in nums: goes over every number in the array. Inside, count[num] = count.get(num, 0) + 1 reads the current count for that number. The get(num, 0) part returns 0 if the number is new. Then we add one. So after this loop, count knows every number’s frequency.

The line buckets = [[] for _ in range(n + 1)] makes a list of empty lists. We need indexes from 0 to n, so we make n + 1 slots. Index freq will hold every number that appears freq times.

The loop for num, freq in count.items(): reads each number and its count. Then buckets[freq].append(num) drops the number into the slot that matches its count. So a number seen three times lands in buckets[3].

The loop for freq in range(n, 0, -1): walks the slots from the highest count down to 1. We want the most frequent numbers first, so we start from the top. Inside, we add each number to result. The moment len(result) == k, we return. So we stop as soon as we have enough.

⏱️ Time and Space Complexity

Counting is one pass, so that part is O(n). Sorting orders every unique number, so it adds O(n log n). The heap keeps only k items, so it costs O(n log k). The bucket method never sorts, so it stays at O(n). All of them need extra memory to hold the counts, which is O(n) space.

🧩 Key Takeaways

• ✅ First count every number with a hash map. That part is always O(n).
• ✅ Sorting the counts works but costs O(n log n), which is more than you need.
• ✅ A heap of size k drops the cost to O(n log k) when k is small.
• ✅ Bucket sort uses the count as an index, so it reaches O(n) time with no sorting.
• ✅ Talk through all three approaches in an interview to show how you improve a solution.

🚀 What’s Next?

• Valid Sudoku
• Subdomain Visit Count