Solutions

# Sorting, min-heap or bucket sort
# heap,bucket-sort
# Sorting, O(nlogn) time, O(1) space
def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for num in nums:
        count[num] = 1 + count.get(num, 0)

    arr = []
    for num, cnt in count.items():
        arr.append([cnt, num])
    arr.sort()

    res = []
    while len(res) < k:
        res.append(arr.pop()[1])
    return res

# Min-heap, O(nlog k) time, O(n+k) space
import heapq
def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for num in nums:
        count[num] = 1 + count.get(num, 0)

    min_heap = []
    for num, cnt in count.items():
        heapq.heappush(min_heap, (cnt, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
        # or avoid popping by inserting with -cnt

    res = []
    while min_heap:
        res.append(heapq.heappop(min_heap)[1])
    return res

# Bucket sort, O(n) time, O(n) space
def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for num in nums:
        count[num] = 1 + count.get(num, 0)

    bucket = [[] for _ in range(len(nums) + 1)]
    for num, cnt in count.items():
        bucket[cnt].append(num)

    res = []
    for i in range(len(bucket) - 1, 0, -1):
        for num in bucket[i]:
            res.append(num)
            if len(res) == k:
                return res
    return res