347. Top K Frequent Elements

347

MediumArrays and HashingHash map + bucket sortFrequency then bucket by count

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order and is guaranteed to be unique.

Open official problem prompt ↗

In plain English

Return the k values that occur most often in the array.

Picture it like this

Like sorting mail into pigeonholes labeled by how many letters each recipient got, then reading off the fullest pigeonholes first until you have named k recipients.

Example

Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Why: 1 occurs three times and 2 occurs twice, the two highest frequencies, so they are the top 2.

Constraints

1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= number of distinct elements in numsThe answer is guaranteed to be unique

Pattern lesson

See the pattern, then code

Frequency then bucket by count

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. A value cannot appear more than n times, so index an array of buckets by frequency and read them from highest to lowest to collect the top k without a comparison sort.

New words, made simpleKnow these before the algorithm

Frequency: How many times a value appears in the array.
Bucket sort: Placing items into buckets keyed by an integer property, here frequency, to avoid comparison sorting.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort by frequency

Simple but the sort is slower than necessary.

Count values then sort the distinct values by count descending and take the first k.

Time O(n log n)Space O(n)

Heap of size k

Good when k is small, but not linear.

Push counts into a min-heap of size k, evicting the smallest.

Time O(n log k)Space O(n)

Best choiceBucket by frequency

Linear time because frequencies are bounded by n.

Index buckets by count and read from the top down.

Time O(n)Space O(n)

The rule we keep true

Invariant

Every value sits in exactly one bucket whose index equals its frequency, so scanning buckets from high to low visits values in non-increasing frequency order.

Why this is correct

Reasoning

Frequencies range only from 1 to n, so an array of n+1 buckets can hold each value at its exact count with no collisions in ordering. Reading buckets from index n downward produces values sorted by frequency, and because the answer is guaranteed unique, taking the first k is correct.

The algorithm in three movesSay these aloud before coding

1Count the frequency of every value

count={1:3,2:2,3:1}

2Create buckets indexed 0..n and place each value in the bucket equal to its frequency

bucket[3]=[1] bucket[2]=[2] bucket[1]=[3]

3Walk buckets from highest frequency down, collecting values

collect 1 then 2 -> [1,2]

4Stop once k values have been gathered

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1:30

2:21

3:12

1 · Read[1,1,1,2,2,3]

2 · AskHow often does each value appear?

3 · Update state{1:3, 2:2, 3:1}

4 · ResultFrequencies established.

Key takeaway

Values sit in buckets keyed by frequency; scanning from the top yields the k most frequent.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Frequency map
Counter tallies each value's occurrences in one pass.
2
Lines 6-8Fill buckets
Each value is dropped into the bucket indexed by its frequency, so position encodes rank.
3
Lines 9-15Harvest top k
Scanning from the highest possible frequency downward collects values until k are gathered, then returns immediately.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k equals the number of distinct values returns all of them
All elements identical yields a single value in the top bucket
Negative values are valid keys in the count map
Every element distinct means each has frequency 1 and any k of them qualify

Common beginner mistakes

Sizing the bucket array to n instead of n+1, since frequency can equal n
Continuing to scan after k items are collected instead of returning early
Sorting the whole count map when bucketing already gives linear time
Assuming a specific output order; the problem allows any order

Check your understanding

Why is bucket sort by frequency linear here when general sorting is n log n?

PyPython 3 · solution.py

Optimal

1from collections import Counter23class Solution:4    def topKFrequent(self, nums: list[int], k: int) -> list[int]:5        count = Counter(nums)6        buckets = [[] for _ in range(len(nums) + 1)]7        for num, freq in count.items():8            buckets[freq].append(num)9        result = []10        for freq in range(len(nums), 0, -1):11            for num in buckets[freq]:12                result.append(num)13                if len(result) == k:14                    return result15        return result

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaGoogleYelp

Top K Frequent Elements

Top K Frequent Elements

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing