Top K Frequent Elements

Count frequencies with a hash map, then sort the items by frequency and take the top k.

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        ordered = sorted(counts.items(), key=lambda pair: -pair[1])
        return [num for num, _ in ordered[:k]]

Counting is O(n), but sorting the (at most n) distinct counts is O(n log n) — and we only actually needed the top k, not a full ordering of every frequency.

A count can never exceed n (the array length), so instead of sorting, create n + 1 buckets indexed by frequency and drop each number into the bucket matching its count. Reading the buckets from highest frequency down and collecting numbers until we have k gives the answer without ever comparing counts against each other.

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in counts.items():
            buckets[freq].append(num)

        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result

Watch each distinct number drop into the bucket that matches its frequency, then the scan walk downward from the highest bucket until k numbers are collected.

After counting, bucket 3 holds [1], bucket 2 holds [2], and bucket 1 holds [3]. Reading from bucket index 6 down to 1 and stopping once k = 2 numbers are collected yields 1 (from bucket 3) then 2 (from bucket 2) — [1, 2].

Correctness: every distinct number lands in exactly one bucket, indexed by its true frequency. Scanning buckets from the highest index down visits numbers in strictly non-increasing frequency order, so the first k numbers collected are exactly the k most frequent.

Complexity: counting is O(n); placing each of the at most n distinct numbers into a bucket is O(n); reading buckets visits at most n + 1 buckets and n numbers total — O(n) time overall, meeting the follow-up. Counts and buckets together hold O(n) entries — O(n) space.