Skip to main content
DSA patterns

Top K Frequent Elements

mediumArrays and hashing Must-doMetaDatadogSplunkUber

Problem statement

You are given an array of integers nums and an integer k. Return the k values that appear most often in nums. You can return them in any order — the set of k values is guaranteed to be unique, so there's no ambiguity about which ones belong in the answer.

Think of it as finding the k busiest hosts in a list of request logs, or the k most common error codes in a day's logs: you don't care about the full ranking, only which values sit in the top k.

Examples

Example 1

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

Output: [1,2]

Explanation: 1 appears 3 times, 2 appears 2 times, 3 appears once. The two most frequent values are 1 and 2.

Example 2

Input: nums = [1], k = 1

Output: [1]

Explanation: There is only one value, so it is trivially the most frequent.

Example 3

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

Output: [1,2]

Explanation: 1 and 2 each appear 4 times, 3 appears twice. The top 2 are 1 and 2 — order doesn't matter.

Hints

Hint 1: Start by counting how many times each number appears — a hash map from value to count gets you that in one pass.

Approach

Optimal: Bucket sort by frequency

Intuition

A count can never be larger than the length of nums — if every value were the same, the count would be n, and it can't go higher than that. That fact means you can skip comparisons entirely: make an array of "buckets" indexed by frequency, from 0 up to n, and drop each value into the bucket that matches its count. Then walk the buckets from the highest frequency down to the lowest, collecting values as you go, and stop once you have k. The bucket index does the sorting for you, so the whole thing runs in linear time — no heap, no full sort.

Steps

  1. Count frequencies with a hash map, same as before.
  2. Create a list of n + 1 empty buckets, indexed 0 through n.
  3. For each value, append it to buckets[count].
  4. Walk the buckets from index n down to 1. Add every value in the current bucket to the answer.
  5. Stop as soon as the answer has k values.

Dry run

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

counts = {1: 3, 2: 2, 3: 1} → buckets[3] = [1], buckets[2] = [2], buckets[1] = [3]

Walking from bucket 6 down: buckets 6, 5, 4 are empty; bucket 3 has [1] → add 1 (answer = [1]); bucket 2 has [2] → add 2 (answer = [1, 2]) → length equals k, stop.

Edge cases: if every value in nums is distinct, every value lands in bucket 1, and you simply take the first k of them — the problem's guarantee that the answer is unique means there's no ambiguity about which ones to take. A single-element array puts that element in bucket 1 and returns it right away.

Complexity

Time O(n) - counting is one pass over nums. Building the buckets is one more pass over at most n distinct values. Walking the buckets from the highest index down until k elements are collected is at most one more O(n) pass.

Space O(n) - the count map holds at most n entries, and the bucket array holds n + 1 buckets whose contents together hold at most n values combined.

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        n = len(nums)
        buckets: list[list[int]] = [[] for _ in range(n + 1)]
        for value, count in counts.items():
            buckets[count].append(value)

        result = []
        for count in range(n, 0, -1):
            for value in buckets[count]:
                result.append(value)
                if len(result) == k:
                    return result
        return result


if __name__ == "__main__":
    print(sorted(Solution().topKFrequent([1, 1, 1, 2, 2, 3], 2)))  # [1, 2]
    print(sorted(Solution().topKFrequent([1], 1)))  # [1]
    print(sorted(Solution().topKFrequent([1, 2, 1, 2, 1, 2, 3, 1, 3, 2], 2)))  # [1, 2]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "k most frequent" / "top k" over an array, order doesn't matter
  • Idea: count with a hash map, then bucket by frequency (bucket index = count) and read off the top k from the highest bucket down — no sorting needed
  • Cost: O(n) time, O(n) space with bucket sort; O(n log k) time, O(n + k) space with a size-k min-heap
  • Trap: sorting every distinct value by count is O(n log n) and passes the base problem, but misses the follow-up's O(n) bound — the count is bounded by n, which is what makes bucket sort possible

Interview follow-ups

  • nums arrives as a continuous stream and you need the current top k at any moment, not just once at the end.

    Keep the running count map as before, and maintain a min-heap of size k alongside it. On each new value, update its count in the map; if that value's new count would place it in the current top k, push it onto the heap and pop the smallest if the heap now exceeds size k. The catch is that a value's count can increase after it's already been pushed once, so in practice you'd use a heap that supports "increase the priority of an existing entry" (an indexed heap) rather than the plain heap used here, so old, stale entries for the same value don't pile up.

  • What if nums has billions of values and doesn't fit in memory?

    Split the values into chunks that each fit in memory, and for each chunk compute a local count map and write out the top few candidates. Merge the partial results the way MapReduce combines partial counts: sum the counts for the same value across chunks, then run the bucket-sort or heap approach on the merged counts. If you only need an approximate answer and want to avoid ever holding the full set of distinct values, a Count-Min Sketch can estimate frequencies in fixed memory at the cost of some accuracy.

Frequently asked questions

Finding the k most common values shows up constantly in operations work: the top-k noisiest hosts in a request log, the most frequent error codes in a day's logs, or the busiest endpoints in an API gateway. It's a fast way to check whether an interviewer knows that a full sort is wasted effort when you only need a handful of values — bucket sort or a bounded heap gets there without ranking everything.

It doesn't, because the problem only asks for a set of k values with no required order, and it guarantees that answer is unique — meaning no value sits exactly on the boundary between "in the top k" and "not in the top k" with a tie you'd need to break. So taking any values from a bucket, in any order, until you reach k is always correct.

You could push every (count, value) pair onto a max-heap and pop the top k, but that heap can grow to size n, so building it costs O(n log n) — no better than sorting. The min-heap trick only pays off because it's kept capped at size k, which is what brings the cost down to O(n log k).

A hash map gives O(1) average-case lookups and inserts, so one pass that reads each of the n values once and updates its count costs O(n) total. This holds no matter how many distinct values there are or how large the numbers are — the cost depends only on how many values you read, not on their range.