Top K Frequent Elements Explained: Finding Top 2 in [1, 1, 1, 2, 2, 3]

Imagine you are handed an inventory log of items that scan repeatedly, and you need to surface the most popular ones instantly. Consider our working example: given nums = [1, 1, 1, 2, 2, 3] and $k=2$, our goal is to return the $k$ values with the highest frequency, which is [1, 2] because 1 appears three times and 2 appears twice.

If you approach this without a structured plan, your first instinct might be to sort the entire collection by how often each element appears. But sorting a massive dataset just to pluck off the top two elements wastes precious computational cycles on ordering elements you do not even care about. As datasets grow, waiting for a full sort becomes a severe bottleneck.

We need a way to track counts efficiently and isolate only the top items without paying the heavy tax of a full sort. Understanding how to handle this efficiently is what the Top K frequent elements pattern is all about.

nums = [1, 1, 1, 2, 2, 3]
k = 2
# Expected result: [1, 2]

When we look at our working example, $\text{nums}=[1,1,1,2,2,3]$ and $k=2$, we are not just searching for raw values. We are building a two-tier relationship: first from element to frequency, and then from frequency back to elements.

In our frequency map, the raw elements map directly to their tally:

To find the top 2 frequent elements, our mental model shifts from looking at the numbers themselves to looking at their frequency buckets. Imagine an array of empty buckets where the index represents how many times an element appeared. Element 3 falls into bucket

3. By inspecting these buckets from the highest frequency down to the lowest, we can easily collect our target of $k=2$ items without sorting every single pair.

Let us trace our locked example from start to finish using the bucket sort approach. We start with our Given: $\text{nums}=[1,1,1,2,2,3]$ and $k=2$. Our goal is to return the two values with the highest frequency.

Given

- $\text{nums}=[1,1,1,2,2,3]$
- $k=2$
- Length $n=6$

Steps

1. Build the frequency map: Count how many times each element appears in $\text{nums}$.
- $1\to 3$
- $2\to 2$
- $3\to 1$

- $\text{buckets}=[[],[],[],[],[],[],[]]$ (indices 0 to 6)

- Bucket 1: $[3]$ (since element 3 appears 1 time)
- Bucket 2: $[2]$ (since element 2 appears 2 times)
- Bucket 3: $[1]$ (since element 1 appears 3 times)
4. Collect from highest bucket down: Scan $\text{buckets}$ from right to left (index 6 down to 0) and append elements to our result list until we reach size $k=2$.

- Index 3: contains $[1]$. Result becomes $[1]$. Length is $1<2$.
- Index 2: contains $[2]$. Result becomes $[1,2]$. Length is $2==k$, so we stop.

Result

- $[1,2]$ (or $[2,1]$ depending on inner order).

Based on this exact trace, what would be the intermediate bucket state if we changed $k=1$ instead of 2?

Try this: Given nums = [1, 1, 1, 2, 2, 3] and k = 1, trace which bucket will supply the final result and list the elements collected.

Now that you have traced the frequency map and bucket collection for $\text{nums}=[1,1,1,2,2,3]$ with $k=2$, it is time to test your mental model on a slightly modified variant. Changing the distribution of elements shifts which bucket indices populate, but the underlying frequency-to-bucket mechanics remain identical.

Work through the prompt below using pencil and paper. Map out the exact frequency counts first, build your bucket array mentally or on scratch paper, and collect the top $k$ elements from right to left.

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    # Implement frequency map and bucket collection here
    pass

Now that you have mastered tracking frequencies and scanning buckets for the working example $1,1,1,2,2,3$, you can apply this exact structural pattern to new domains. The core trick—mapping items to their raw frequencies first, then indexing them by frequency buckets rather than sorting the entire dataset—appears anywhere you need real-time analytics without the $O(n\log n)$ tax.

Imagine you are building a log analysis dashboard for an API gateway. Instead of integers, your input is a stream of IP addresses making requests over a minute. You need to flag the top $k=2$ most active IPs for rate-limiting review. Just as you built a frequency map $1:3,2:2,3:1$ for our integers, you build a frequency map of IP strings. You then route those IPs into frequency buckets where the bucket index represents the request count. Scanning from the highest bucket down immediately surfaces your top abusers.

This transfer works because frequency counting and bucket sorting are agnostic to data types. Whether your elements are numbers, strings, or database record IDs, the bottleneck is always counting. Once counts are known, bucket sorting bypasses comparison sorting entirely by leveraging the maximum possible frequency $n$ as a finite array boundary.