Top K Frequent Elements

01 · Question

Given an integer array nums and an integer k, return the k most frequent elements.

02 · Analysis

Count each value, then retain the k highest-frequency (frequency, value) pairs in a min-heap. Removing the lowest frequency preserves the best candidates; ties may be returned in any order. For U distinct values, time is expected O(n + U log(k+1)), space O(U+k), including the frequency map. Require 1 <= k <= U.

03 · Solution

Reference solution

1import heapq
2
3def topKFrequent(nums: List[int], k: int) -> List[int]:
4    freq = {}
5    for x in nums:
6        freq[x] = freq.get(x, 0) + 1
7
8    heap = []
9    for x, f in freq.items():
10        heapq.heappush(heap, (f, x))
11        if len(heap) > k:
12            heapq.heappop(heap)
13
14    return [x for (_, x) in heap]

Kth Largest Element in an Array

K Closest Points to Origin