DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Top K Frequent Elements

mediumArrays and hashing Must-do

Problem statement

Given a list of integers and a number k, return the k values that appear most often. The answer is guaranteed to be unique, and you can return it in any order.

Examples

Example 1

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

Output: [1, 2]

Explanation: 1 appears three times and 2 appears twice.

Approach

Optimal

This is two steps. First count how often each value appears, using a dictionary. Then pick the k biggest counts. Sorting all counts works, but a heap of size k is cheaper when k is small, and bucket sort by frequency gets it down to linear time.

  1. Count every value with a Counter (a dictionary of value -> frequency).
  2. Ask for the k highest counts: heapq.nlargest keeps a small heap of size k while scanning the counts.
  3. Return just the values from those k entries.
  4. Linear-time alternative: make buckets indexed by frequency, drop each value into its bucket, then read buckets from the highest frequency down until you have k values.
ComplexityTime O(n log k) with a heap, O(n) with bucketsSpace O(n)
Python
from collections import Counter
import heapq
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums) # value -> frequency
return [value for value, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]
# O(n) bucket version
def top_k_frequent_buckets(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)] # index = frequency
for value, freq in counts.items():
buckets[freq].append(value)
result = []
for freq in range(len(buckets) - 1, 0, -1):
for value in buckets[freq]:
result.append(value)
if len(result) == k:
return result
return result

Frequently asked questions

"Which 10 errors happened most in the last hour?" and "Which 5 IPs sent the most requests?" are this exact problem, and among the most common practical SRE questions. In interviews, expect the follow-up: what if the log is too big for memory? Stream it line by line into the counter rather than loading the whole file.

  • Sorting the whole list of counts when only the top k are needed.
  • Returning (value, count) pairs when the task asks for values only.
  • Reading a huge log file into memory before counting, instead of streaming it.