Leetcode - 347. Top K Frequent Elements

🚀 Approach: Bucket Sort (Linear Time)

Instead of sorting elements by frequency (which takes O(n log n)), we use a bucket sort trick to solve it in O(n).

Steps:

1. Count frequencies using a Map.
2. Group numbers by their frequency into a bucket array.
3. Traverse the bucket in reverse order (high frequency to low) and collect top k elements.

---

✅ Code (JavaScript):

class Solution {
  /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number[]}
   */
  topKFrequent(nums, k) {
    const freqMap = new Map();

    // Step 1: Count frequency
    for (const num of nums) {
      freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    // Step 2: Bucket where index = frequency
    const bucket = Array(nums.length + 1).fill().map(() => []);
    for (const [num, freq] of freqMap.entries()) {
      bucket[freq].push(num);
    }

    // Step 3: Collect top k from highest freq down
    const result = [];
    for (let i = bucket.length - 1; i >= 0 && result.length < k; i--) {
      if (bucket[i].length > 0) {
        result.push(...bucket[i]);
      }
    }

    return result.slice(0, k);
  }
}

---

⏱️ Time & Space Complexity

• Time Complexity: O(n)

  • Frequency count: O(n)
  • Bucket fill: O(n)
  • Bucket traversal: O(n)

• Space Complexity: O(n)

  • Frequency map: O(n)
  • Bucket array: O(n)
  • Result array: O(k)

---