[LeetCode/Python] 347. Top K Frequent Elements

📌 Problem

[LeetCode] 347. Top K Frequent Elements

📌 Solution

Solution 1: Use Counter

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        ans = [num for num, freq in cnt.most_common(k)]
        return ans

• 코드는 간단함
• but.. 시간복잡도가 넘 큼..

Complexity

• Time: $O(n + u \log k)$
  (Counting all elements and extracting top-k frequent items)

• Space: $O(u + k) ≈ O(n)$
  (Frequency map plus output list)
  $n$ = length of nums, $u$ = number of unique elements

Solution 2: Bucket Sort ⭐️

Idea

1. freq[x] = x의 등장 횟수
   Count the frequency of each element: freq[x] = number of times x appears

2. buckets[c] = 빈도가 c인 값들
   Create buckets by frequency: buckets[c] = elements that appear c times

3. 큰 빈도부터 내려오며 k개 모으면 끝
   Traverse from the highest frequency down and collect k elements

Code

from typing import List
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)  # value -> count

        # buckets[count] = list of values with that count
        buckets = [[] for _ in range(len(nums) + 1)]
        for val, cnt in freq.items():
            buckets[cnt].append(val)

        ans = []
        # 높은 빈도부터 내려오며 채우기
        for cnt in range(len(buckets) - 1, 0, -1):
            for val in buckets[cnt]:
                ans.append(val)
                if len(ans) == k:
                    return ans

        return ans  # (문제 조건상 보통 여기 도달 안 함)

Complexity

• Counting: $O(n)$
• Bucket filling: $O(u)$ where $u$ is the number of unique elements ($u ≤ n$)
• Traversing from the end: $O(n)$ in the worst case

• Time: $O(n)$
• Space: $O(n)$ (Bucket + Counter)

Solution 3: Min-Heap

Idea

• (값, 빈도) 중 빈도만 기준으로 크기 k짜리 최소힙 유지
  Maintain a size-k min-heap based on frequency (store (value, freq))
• 힙 크기가 k 초과하면 가장 작은 빈도 제거
  If the heap size exceeds k, remove the smallest-frequency element

Code

from typing import List
from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)

        heap = []  # (count, value)
        for val, cnt in freq.items():
            heapq.heappush(heap, (cnt, val))
            if len(heap) > k:
                heapq.heappop(heap)

        return [val for cnt, val in heap]

Complexity

• Time: $O(n + u \log k) (≈ O(n \log k))$
  where $u$ is the number of unique elements
• Space: $O(u + k) (≈ O(n))$