Top K Frequent Elements — tìm K phần tử xuất hiện nhiều nhất. Vì sao bucket sort nhanh hơn heap ở đây?

Ý tưởng: Đếm tần suất bằng HashMap. Hai cách lấy top-K:
- Min-heap kích thước K: duyệt các tần suất, giữ heap K phần tử lớn nhất → O(n log K).
- Bucket sort: tần suất tối đa là n, nên tạo mảng buckets[freq] rồi quét từ cao xuống thấp lấy đủ K → O(n).

Vì sao bucket nhanh hơn: chỉ số bucket bị chặn bởi n (tần suất không thể vượt số phần tử), nên ta "sắp xếp" tần suất bằng đếm phân phối, bỏ được hệ số log.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>()
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1)
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => [])
  for (const [num, f] of freq) buckets[f].push(num)
  const res: number[] = []
  for (let f = buckets.length - 1; f >= 0 && res.length < k; f--)
    for (const num of buckets[f]) { res.push(num); if (res.length === k) break }
  return res
}

Độ phức tạp: bucket O(n) thời gian & O(n) bộ nhớ.

Lưu ý: Heap vẫn là lựa chọn tốt khi K rất nhỏ so với n hoặc dữ liệu streaming; bucket sort cần biết trước giới hạn tần suất.

Idea: Count frequencies with a HashMap. Two ways to get top-K:
- Min-heap of size K: iterate frequencies, keep the K largest → O(n log K).
- Bucket sort: max frequency is n, so build buckets[freq] and scan high→low picking K → O(n).

Why bucket is faster: the bucket index is bounded by n (frequency can't exceed the element count), so we "sort" frequencies by distribution counting, dropping the log factor.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>()
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1)
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => [])
  for (const [num, f] of freq) buckets[f].push(num)
  const res: number[] = []
  for (let f = buckets.length - 1; f >= 0 && res.length < k; f--)
    for (const num of buckets[f]) { res.push(num); if (res.length === k) break }
  return res
}

Complexity: bucket O(n) time & O(n) space.

Note: A heap is still good when K is tiny vs n or for streaming data; bucket sort needs a known frequency bound.