leetcode-347 Top K Frequent Elements

# Given an integer array nums and an integer k, return the k most frequent
# elements. You may return the answer in any order.
#
# Example 1:
# Input: nums = [1,1,1,2,2,3], k = 2
# Output: [1,2]
#
# Example 2:
# Input: nums = [1], k = 1
# Output: [1]
#
# Constraints:
# 1 <= nums.length <= 10^5
# -10^4 <= nums[i] <= 10^4
# k is in the range [1, number of unique elements]
# It is guaranteed that the answer is unique.

import heapq
from collections import Counter

class Solution:
    # Approach 1: Heap
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        count = Counter(nums)

        # Min-heap of size k, storing (frequency, number)
        heap = []

        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)

        # Extract numbers from heap
        return [num for freq, num in heap]

    # Approach 2: Using heapq.nlargest (cleaner)
    def topKFrequent2(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        return heapq.nlargest(k, count.keys(), key=count.get)

    # Approach 3: Bucket Sort - O(n) time!
    def topKFrequent3(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # bucket[i] = list of numbers with frequency i
        bucket = [[] for _ in range(len(nums) + 1)]

        for num, freq in count.items():
            bucket[freq].append(num)

        # Collect k most frequent from high frequencies
        result = []
        for freq in range(len(bucket) - 1, 0, -1):
            for num in bucket[freq]:
                result.append(num)
                if len(result) == k:
                    return result

        return result

# Heap: Time O(n log k), Space O(n)
# Bucket Sort: Time O(n), Space O(n)
#
# Key Pattern: Heap + HashMap for "top k frequent" problems
# Bucket sort is optimal but less general than heap approach