What is the brute force approach and complexity for Top K Frequent Elements?

Count the values, sort all (count, value) pairs, take the first k with time complexity O(N + U log U) and space complexity O(U).

What is the optimal approach and complexity for Top K Frequent Elements?

Count the values; put each value in the bucket for its count; walk from the highest bucket down with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Top K Frequent Elements?

Look for key signals in the prompt: "k most frequent" indicates Count first. The number that matters is the count, not the value.; "return the k values" indicates Keep only k candidates: a heap of size k, or buckets walked from the top.; "any order" indicates No sort is needed. A heap or a bucket walk gives the set directly.; "the answer is unique" indicates No tie at the k-th place, so no tie-break rule is needed..

Top K Frequent Elements

Medium·LeetCode #347Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTop K by frequency — count map, then a size-k heap or buckets by count

Complexity:O(N + U log U)→O(N)

Key Insight

A count can't be bigger than n, so use the count as the bucket index. bucket[c] lists the values that appear exactly c times. Walk the buckets from n down to 1 and stop once you have k values. No sorting and no heap are needed.

Core Validity Invariant

Each value sits in the bucket for its exact count, so the highest non-empty buckets hold the most frequent values.

Problem

You get an array of integers nums and a number k. Count how often each value appears. Return the k values that appear the most.

The order of the answer does not matter. The problem promises one correct answer: the k-th most frequent value always appears strictly more often than the next one.

Input

An integer array nums, and an integer k.

Output

A list of k values: the most frequent ones. Any order is fine.

Example 1

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

Output: [1, 2]

1 appears 3 times and 2 appears 2 times. 3 appears only once, so it is not in the answer.

Example 2

Input: nums = [1], k = 1

Output: [1]

There is only one value.

Example 3

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

Output: [1, 2]

1 appears 4 times, 2 appears 4 times, and 3 appears 2 times. The top two are 1 and 2.

Constraints

• 1 ≤ nums.length ≤ 10^5
• −10^4 ≤ nums[i] ≤ 10^4
• 1 ≤ k ≤ the number of unique values in nums
• The answer is unique (the problem guarantees it).
• Follow-up: can you do better than O(n log n)?

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Does the question ask about the values themselves, or about how often each value appears?
2.
Can I answer it without sorting every value? What is the smallest thing I need to keep?
3.
If I keep only the best k candidates, should I compare them by the value or by the count?
4.
How many times can one value appear in an array of length n?
5.
Can two values with the same count both belong in the answer? Give a small example.

Brute force approach

Idea

Count every value with a hash map. Then sort all the (count, value) pairs by count, highest first, and take the first k. The sort puts the k biggest counts at the front, but it also orders many values we never need.

Thinking process

1
The question is about how often each value appears, so count first. For nums = [1, 1, 1, 2, 2, 3] the counts are 1 → 3, 2 → 2, 3 → 1.
2
Turn each entry into a (count, value) pair. The count comes first, so sorting compares counts.
3
Sort all the pairs, highest first: (3, 1), (2, 2), (1, 3).
4
Take the first k = 2 pairs: values 1 and 2. Check: 1 appears 3 times and 2 appears 2 times, and 3 appears only once, so these are the two most frequent.
5
This is correct, but it sorts values that we throw away. When k is small, most of that sorting is wasted. The next approach keeps only k candidates.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Count how many times each value appears.
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;

        // List every (count, value) pair and sort ALL of them, highest count first.
        // The count is the first field, so the sort compares counts, not values.
        vector<pair<int, int>> pairs;
        for (auto& [value, c] : freq) pairs.push_back({c, value});
        sort(pairs.begin(), pairs.end(), greater<pair<int, int>>());

        // The first k pairs have the k biggest counts.
        vector<int> ans;
        for (int i = 0; i < k; i++) ans.push_back(pairs[i].second);
        return ans;
    }
};

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

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Count how many times each value appears.
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        // List every (count, value) pair and sort ALL of them, highest count first.
        List<Map.Entry<Integer, Integer>> pairs = new ArrayList<>(freq.entrySet());
        pairs.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));

        // The first k pairs have the k biggest counts.
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pairs.get(i).getKey();
        }
        return ans;
    }
}

from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count how many times each value appears.
        freq = Counter(nums)

        # List every (count, value) pair and sort ALL of them, highest count first.
        pairs = [(c, val) for val, c in freq.items()]
        pairs.sort(reverse=True)

        # The first k pairs have the k biggest counts.
        return [val for _, val in pairs[:k]]

export function topKFrequent(nums: number[], k: number): number[] {
    // Count how many times each value appears.
    const freq = new Map<number, number>();
    for (const x of nums) {
        freq.set(x, (freq.get(x) || 0) + 1);
    }

    // List every (count, value) pair and sort ALL of them, highest count first.
    const pairs: [number, number][] = [];
    for (const [val, c] of freq.entries()) {
        pairs.push([c, val]);
    }
    pairs.sort((a, b) => b[0] - a[0]);

    // The first k pairs have the k biggest counts.
    const ans: number[] = [];
    for (let i = 0; i < k; i++) {
        ans.push(pairs[i][1]);
    }
    return ans;
}

Complexity

Time O(N + U log U)Space O(U)

N is the array length and U is the number of distinct values (U ≤ N). Counting costs O(N). Sorting the U pairs costs O(U log U), even when k = 1.

Better approach

Why brute force is slow

The brute force sorts every distinct value, even though only k of them are kept. With 10^4 distinct values and k = 2, it orders 10^4 pairs just to keep 2.

What repeated work are we doing?

The sort also puts the low-count values in order, and those are thrown away. Most of the sorting effort goes to values that never reach the answer.

What information can we reuse?

Keep only k candidates in a heap. Each value costs one push and at most one pop, each O(log k), instead of O(log U) inside a full sort.

New approach

Idea

Count the values. Then go through the counts once and keep a min-heap of at most k entries, each a (count, value) pair. When the heap grows past k, pop the entry with the smallest count. At the end the heap holds the k most frequent values.

Thinking process

1
Sorting all the pairs does more than we need. We only keep k values, so we only need k candidates at any time.
2
A min-heap keeps its smallest item on top. Key it on the count, so the top is the weakest candidate: the first one to drop.
3
Check on [1, 1, 1, 2, 2, 3] with k = 2: push (3, 1) and (2, 2). The heap has size 2. Next push (1, 3): size is now 3 > 2, so pop the top, which is (1, 3). The heap keeps values 1 and 2. Correct.
4
The key is the count, not the value. A heap keyed on the value would keep the biggest numbers, which answers a different question.
5
Each value is pushed once. The heap never holds more than k + 1 items, so each push or pop costs O(log k).

Visual

The heap is shown in pop order: the top (left) is the smallest count, the first one to evict. Each cell is value:count. Green = just pushed; orange = the heap grew past k, so the top is dropped. The count map is walked in first-seen order.

Min-heap keyed on the countnums = [1, 1, 1, 2, 2, 3, 4, 4, 5], k = 3step 1/17

nums

▲i

min-heap on count (size ≤ k = 3)

count map (value → count)

1:1

Counting: 1 has been seen 1 time

nums[0] = 1. Its count is now 1. The heap stays empty while we count.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;

        // Min-heap of (count, value) with at most k entries.
        // The count comes first in the pair, so the top is the smallest COUNT:
        // the weakest candidate, and the first one to evict.
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        for (auto& [value, c] : freq) {
            heap.push({c, value});
            if ((int)heap.size() > k) heap.pop();   // drop the weakest of the k + 1
        }

        // The heap now holds exactly the k most frequent values, in no useful order.
        vector<int> ans;
        while (!heap.empty()) {
            ans.push_back(heap.top().second);
            heap.pop();
        }
        return ans;
    }
};

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        // Min-heap of (count, value) with at most k entries.
        // The top is the smallest COUNT: the weakest candidate, and the first one to evict.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.add(new int[] { entry.getValue(), entry.getKey() });
            if (heap.size() > k) {
                heap.poll(); // drop the weakest of the k + 1
            }
        }

        // The heap now holds exactly the k most frequent values, in no useful order.
        int[] ans = new int[k];
        int idx = 0;
        while (!heap.isEmpty()) {
            ans[idx++] = heap.poll()[1];
        }
        return ans;
    }
}

from collections import Counter
import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)

        # Min-heap of (count, value) with at most k entries.
        # The top is the smallest COUNT: the weakest candidate, and the first one to evict.
        heap: List[tuple[int, int]] = []
        for val, c in freq.items():
            heapq.heappush(heap, (c, val))
            if len(heap) > k:
                heapq.heappop(heap)  # drop the weakest of the k + 1

        # The heap now holds exactly the k most frequent values, in no useful order.
        return [val for _, val in heap]

type Pair = [number, number]; // [count, value]

class MinHeap {
    private data: Pair[] = [];

    push(val: Pair): void {
        this.data.push(val);
        this.bubbleUp(this.data.length - 1);
    }

    pop(): Pair | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }

    size(): number {
        return this.data.length;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.data[parent][0] > this.data[idx][0]) {
                [this.data[parent], this.data[idx]] = [this.data[idx], this.data[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.data.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.data[left][0] < this.data[smallest][0]) smallest = left;
            if (right < len && this.data[right][0] < this.data[smallest][0]) smallest = right;
            if (smallest !== idx) {
                [this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function topKFrequent(nums: number[], k: number): number[] {
    const freq = new Map<number, number>();
    for (const x of nums) {
        freq.set(x, (freq.get(x) || 0) + 1);
    }

    // Min-heap of (count, value) with at most k entries.
    // The top is the smallest COUNT: the weakest candidate, and the first one to evict.
    const heap = new MinHeap();
    for (const [val, c] of freq.entries()) {
        heap.push([c, val]);
        if (heap.size() > k) {
            heap.pop(); // drop the weakest of the k + 1
        }
    }

    // The heap now holds exactly the k most frequent values, in no useful order.
    const ans: number[] = [];
    while (heap.size() > 0) {
        ans.push(heap.pop()![1]);
    }
    return ans;
}

Complexity

Time O(N + U log k)Space O(U)

Counting is O(N). Each of the U values costs one push and at most one pop on a heap of size at most k + 1. Since k ≤ U, this is never worse than the brute force.

Optimized approach

Idea

Start from brute force

Brute force sorts every (count, value) pair to find the top k. But the only thing we need from the sort is the order by count, and counts are small whole numbers.

Find the repeated work

The sort compares values again and again, but a count can only be one of the numbers 0 … n. Most of those comparisons order values that will be thrown away anyway.

Define the state — what variables do I need?

freq: Map from value to how many times it appears.
bucket[c]: The values that appear exactly c times, for c = 0 … n.
c: The count we are looking at now. The walk goes from n down to 1.
ans: Values collected so far. The walk stops when it has k of them.

Define validity

Each value sits in the bucket for its exact count, so the highest non-empty buckets hold the most frequent values.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Count every value into `freq`.

A value's count is only known after all of nums has been read.

For each value and its count c

bucket[c].push_back(value)

Each value goes into exactly one bucket, the one for its count. So no value is lost or counted twice.

c goes from n down to 1, while ans has fewer than k values

Add the values in bucket[c] to ans until ans has k values.

Every value in bucket[c] has the same count c. Every higher bucket was already taken or was empty, so these are the next most frequent values.

What does the current window add to the answer?

Each bucket either is empty or adds its values in one go. Every bucket is visited once, so the walk costs O(n).

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;

        // bucket[c] = the values that appear exactly c times.
        // No value can appear more than n times, so indexes 0 … n are enough.
        vector<vector<int>> bucket(n + 1);
        for (auto& [value, c] : freq) bucket[c].push_back(value);

        // Walk from the highest count down. The first k values we meet are the answer.
        vector<int> ans;
        for (int c = n; c >= 1 && (int)ans.size() < k; c--) {
            for (int value : bucket[c]) {
                if ((int)ans.size() < k) ans.push_back(value);
            }
        }
        return ans;
    }
};

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

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.put(x, freq.getOrDefault(x, 0) + 1);
        }

        // bucket[c] = the values that appear exactly c times.
        // No value can appear more than n times, so indexes 0 … n are enough.
        @SuppressWarnings("unchecked")
        List<Integer>[] bucket = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            bucket[i] = new ArrayList<>();
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            bucket[entry.getValue()].add(entry.getKey());
        }

        // Walk from the highest count down. The first k values we meet are the answer.
        int[] ans = new int[k];
        int idx = 0;
        for (int c = n; c >= 1 && idx < k; c--) {
            for (int value : bucket[c]) {
                if (idx < k) {
                    ans[idx++] = value;
                }
            }
        }
        return ans;
    }
}

from collections import Counter
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        freq = Counter(nums)

        # bucket[c] = the values that appear exactly c times.
        # No value can appear more than n times, so indexes 0 … n are enough.
        bucket: List[List[int]] = [[] for _ in range(n + 1)]
        for val, c in freq.items():
            bucket[c].append(val)

        # Walk from the highest count down. The first k values we meet are the answer.
        ans: List[int] = []
        for c in range(n, 0, -1):
            for val in bucket[c]:
                if len(ans) < k:
                    ans.append(val)
        return ans

export function topKFrequent(nums: number[], k: number): number[] {
    const n = nums.length;
    const freq = new Map<number, number>();
    for (const x of nums) {
        freq.set(x, (freq.get(x) || 0) + 1);
    }

    // bucket[c] = the values that appear exactly c times.
    // No value can appear more than n times, so indexes 0 … n are enough.
    const bucket: number[][] = Array.from({ length: n + 1 }, () => []);
    for (const [value, c] of freq.entries()) {
        bucket[c].push(value);
    }

    // Walk from the highest count down. The first k values we meet are the answer.
    const ans: number[] = [];
    for (let c = n; c >= 1 && ans.length < k; c--) {
        for (const value of bucket[c]) {
            if (ans.length < k) {
                ans.push(value);
            }
        }
    }
    return ans;
}

Complexity

Time O(N)Space O(N)

Counting is O(N) with a hash map. Filling the buckets costs O(U). The walk visits at most n + 1 buckets and each value once, so the total is O(N). The buckets take O(N) extra space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Count the values, sort all (count, value) pairs, take the first k	O(N + U log U)	O(U)
Better	Count the values; keep a min-heap of at most k (count, value) pairs, keyed on the count	O(N + U log k)	O(U)
Optimal	Count the values; put each value in the bucket for its count; walk from the highest bucket down	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“k most frequent”Count first. The number that matters is the count, not the value.
“return the k values”Keep only k candidates: a heap of size k, or buckets walked from the top.
“any order”No sort is needed. A heap or a bucket walk gives the set directly.
“the answer is unique”No tie at the k-th place, so no tie-break rule is needed.

Count each value+keep the k best by count+count ≤ n → bucket by count→Top K by frequency — count map, then a size-k heap or buckets by count

Kth Largest picks by the value itself. This question picks by how often each value appears, so the key is the count, not the value. A value that appears three times beats a value 9 that appears once. Sort Characters By Frequency reuses the count step, but it needs every character, not only the top k.

Don't make this mistake

Pattern confusion: keying the heap on the value

✗ priority_queue<int, vector<int>, greater<int>> heap; // a heap of values

✓ priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap; // (count, value)

On nums = [1, 1, 1, 2, 2, 3, 4, 4, 5] with k = 3, a heap of values keeps the three biggest numbers: 3, 4 and 5. The right answer is 1, 2 and 4, because 1 appears 3 times and 2 and 4 appear 2 times each. The heap must compare the count, not the value.

Using the value as the bucket index

✗ bucket[value].push_back(value);

✓ bucket[count].push_back(value);

Values can be negative (down to −10^4), so bucket[value] is out of range. A bucket index is a count, which is always between 0 and n.

Walking the buckets from the bottom up

✗ for (int c = 1; c <= n; c++)

✓ for (int c = n; c >= 1; c--)

Walking up collects the least frequent values first. On nums = [1, 1, 1, 2, 2, 3, 4, 4, 5] with k = 3, it takes 3 and 5 (count 1) first, then one count-2 value. The answer must be 1, 2 and 4.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Heap — Top K translate into production architectures and low-level memory mechanics.

LLD Real-World Story

High-Frequency Trading (HFT) Order Book

Price-time priority matching engine powered by heap buckets and tree maps.

Explore Track

C++ Internals

STL Containers & Allocator Internals

std::priority_queue container adapter and underlying heapify memory buffers.

Explore Track

Sort Characters By Frequency