Top K Frequent Elements

Given an integer array, return the k most frequent elements. The order does not matter; any valid answer is accepted.

The key insight: frequency is a counting problem first, a ranking problem second. The machine first builds a Counter — one pass, O(n) — mapping each distinct value to how often it appears. Then it ranks those (value, count) pairs. A min-heap of size k keeps the k most frequent without sorting the whole counter: push each pair, and when the heap exceeds k, pop the least frequent. Whatever remains is the answer set. The heap compares by count, so it never stores a value more than once — distinct keys only.

Approach in steps:

1. Count frequencies with a hash map: O(n).
2. For each (value, count), push onto a min-heap keyed by count; evict the root when the heap size passes k.
3. Return the values remaining in the heap.

import heapq
from collections import Counter
 
def topKFrequent(nums, k):
    counts = Counter(nums)
    heap = []
    for val, cnt in counts.items():
        heapq.heappush(heap, (cnt, val))
        if len(heap) > k:
            heapq.heappop(heap)
    return [val for _, val in heap]

Time is O(n log k), space O(n) for the counter (plus the heap). The heap is always at most k entries, so the ranking step stays small.

Trickiest edge case: single-element input — [1], k = 1 must return [1], and the eviction path must not trigger when the heap is exactly k. Also remember the heap stores (count, value), not values directly; storing values alone would rank by value, not frequency, and return the wrong elements.