Skip to content

Practice Top K Frequent Elements

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Source: Top K Frequent Elements on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

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

# Example 2

Input
nums = [1], k = 1
Output
[1]

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

How to solve Top K Frequent Elements

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Frequencies are bounded by n, so after counting you can drop each distinct value into a bucket indexed by its frequency and read buckets from highest to lowest until k values are collected, with no sorting at all.

Why brute force is not enough

Counting and then sorting the distinct values by frequency is O(n log n) when every value is distinct, and the follow-up explicitly demands better for n up to 10^5. Repeatedly scanning for the most frequent remaining value k times is O(n * k).

Approach

  1. Count occurrences of each value with a hash map; afterward the map holds every distinct value with its exact frequency.
  2. Create n + 1 buckets where bucket f lists the values appearing exactly f times; no frequency exceeds n, so every value has a bucket.
  3. Scan buckets from frequency n down to 1, appending values to the result; the invariant is that every value already added has frequency at least that of any value not yet added.
  4. Stop once the result holds k values; the uniqueness guarantee means no tie-breaking is needed.
  5. If n buckets is too much memory, a min-heap of size k keyed by frequency gives O(n log k), and quickselect on the distinct values gives average O(n).

Walkthrough of Example 1

nums = [1,1,1,2,2,3], k = 2 → [1,2]

  1. Counting gives 1 three times, 2 twice, and 3 once.
  2. Bucket 3 holds [1], bucket 2 holds [2], bucket 1 holds [3]; buckets 4 through 6 are empty.
  3. Scanning down from 6, the first nonempty bucket is 3, so 1 is added; the result has one value, so continue.
  4. Bucket 2 adds 2; the result now has k = 2 values, so stop and return [1,2].

Time and space

Time O(n) · Space O(n). n is nums.length; counting is one pass of expected constant-time map operations, filling and scanning n + 1 buckets is linear, and the map and buckets hold at most n entries.

Interview pitfalls

  • Allocating only n buckets and indexing bucket n out of range when one value fills the array, as in example 2 with a single element.
  • Scanning buckets from low to high, which collects the least frequent values first.
  • Appending an entire bucket that pushes the result past k; the guarantee rules it out here, but tie-heavy variants need an explicit cutoff.
  • Using a max-heap of all distinct values and popping k times, which is O(n log n) in the worst case and does not beat the follow-up bound.
  • Mishandling negative values down to -10^4 by using an array indexed by value without an offset.

Follow-up questions interviewers ask

  • How would you return the k most frequent words with ties broken alphabetically, and how does that change the complexity?
  • If the data streams past faster than memory allows, how would you approximate the top k with a fixed budget?

Further reading on the technique: Bucket sort

Related LeetCode Problems

Practice more problems similar to Top K Frequent Elements.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.