Return the k most frequent elements in an array.

How to think about it

“Top k by some score” is the phrase that should make you say “heap” before you finish reading the question. The interviewer wants to see that you will not sort everything just to take the top slice — sorting is O(n log n) and throws away work you do not need. The sharper instinct is a min-heap capped at size k, which keeps only the k best candidates alive as you scan. And there is a bonus signal hiding in the constraints: array frequencies are bounded by n, which opens a bucket-sort path all the way down to O(n).

Both approaches start the same way — one pass to count frequencies into a hash map. From there the heap version pushes each (freq, element) pair and, whenever the heap grows past k, pops the minimum; the globally least-frequent candidate falls off, so whatever survives is the answer. Why a min-heap when you want the largest? Because the cheapest thing to evict is the smallest, and evicting smalls is how you protect the larges. The bucket version skips comparisons entirely: make n + 1 buckets where bucket[f] holds every element seen exactly f times, then walk the buckets from high frequency down, collecting until you have k.

A worked example

import heapq
from collections import Counter

# --- Approach 1: min-heap, O(n log k) ---
def top_k_heap(nums, k):
    freq = Counter(nums)
    heap = []                              # min-heap of (freq, elem)
    for elem, f in freq.items():
        heapq.heappush(heap, (f, elem))
        if len(heap) > k:
            heapq.heappop(heap)            # evict the least frequent
    return [elem for f, elem in heap]

# --- Approach 2: bucket sort, O(n) ---
def top_k_bucket(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for elem, f in freq.items():
        buckets[f].append(elem)            # index by frequency
    result = []
    for f in range(len(buckets) - 1, 0, -1):   # high freq -> low
        for elem in buckets[f]:
            result.append(elem)
            if len(result) == k:
                return result
    return result

# sorted() only for a stable printout — ties at position k are unspecified
print(sorted(top_k_heap([1, 1, 1, 2, 2, 3], 2)))
print(sorted(top_k_bucket([1, 1, 1, 2, 2, 3], 2)))
print(sorted(top_k_heap([4, 4, 5, 5], 2)))
print(sorted(top_k_heap([7], 1)))

print("freq:", Counter([1, 1, 1, 2, 2, 3]))
print("most_common(2):", Counter([1, 1, 1, 2, 2, 3]).most_common(2))

[1, 2]
[1, 2]
[4, 5]
[7]
freq: Counter({1: 3, 2: 2, 3: 1})
most_common(2): [(1, 3), (2, 2)]

Both methods agree on [1, 2] for the first array: 1 appears three times and 2 twice, so 3 (a single occurrence) is the one left out. The freq line shows the map the algorithms work from, and most_common(2) returns the same top two as (element, count) pairs — proof the library shortcut lands on the identical result. Note the sorted() wrapper around each print: the heap returns its elements in whatever order they happen to sit, so the sort is purely for a reproducible printout, not part of the algorithm.