Top K Frequent Elements

Problem Statement #

Given a non-empty array of integers, return the k most frequent elements.

Constraints:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size
It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique
You can return the answer in any order

Example:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Understanding the Constraints #

Let’s break down what these constraints mean for our solution:

1. K is always valid (1 ≤ k ≤ number of unique elements)

This means you won’t encounter impossible scenarios. This eliminates the need for error checking around invalid k values.

2. Time complexity must be better than O(n log n)

This is a critical constraint that eliminates certain approaches. A simple “sort the entire array and count” approach would be O(n log n), which violates this requirement.

3. The answer is guaranteed to be unique

This means you won’t have ties that make the answer ambiguous. The problem guarantees this won’t happen, so we don’t need to handle tie-breaking logic.

4. You can return the answer in any order

The output doesn’t need to be sorted - [1,2] and [2,1] are both valid answers for the example above.

Optimal Solution: Bucket Sort (O(n)) #

To truly satisfy the time complexity constraint, we use bucket sort:

const topKFrequent = (nums, k) => {
  // Step 1: Build frequency map - O(n)
  const counts = {};
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

  // Step 2: Create buckets - O(n)
  const buckets = Array(nums.length + 1).fill(null).map(() => []);
  for (let num in counts) {
    buckets[counts[num]].push(parseInt(num));
  }

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

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

Key insight: The maximum frequency any element can have is n (all elements are the same). So we create n+1 buckets where bucket[i] contains all elements with frequency i. Then we iterate from the highest frequency bucket down, collecting elements until we have k items.

This achieves true O(n) time complexity!

Alternative Solution: Frequency Count + Sort #

Here’s a more intuitive approach that uses sorting:

const topKFrequent = (nums, k) => {
  const counts = {};
  const sortable = [];
  const result = [];

  // Step 1: Get counts - O(n)
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

  // Step 2: Convert to array and sort - O(m log m) where m = unique elements
  function sortBy(a, b) {
    return b[1] - a[1];
  }

  for (let i in counts) {
    sortable.push([i, counts[i]]);
  }
  sortable.sort(sortBy);

  // Step 3: Create result - O(k)
  for (let i = 0; i < k; i++) {
    result.push(sortable[i][0]);
  }

  return result;
};

Note: This approach has O(n + m log m) complexity where m is the number of unique elements. In the worst case where all elements are unique (m = n), this becomes O(n log n), which technically doesn’t meet the problem’s constraint but works well in practice.

Detailed Breakdown of Bucket Sort Approach #

Step 1: Building the Frequency Map #

for (let num of nums) {
  counts[num] = (counts[num] || 0) + 1;
}

This creates an object where each unique number maps to its frequency.

Example: For [1,1,1,2,2,3], this produces:

{
  1: 3,
  2: 2,
  3: 1
}

Step 2: Creating Frequency Buckets #

const buckets = Array(nums.length + 1).fill(null).map(() => []);
for (let num in counts) {
  buckets[counts[num]].push(parseInt(num));
}

We create an array of buckets where buckets[i] contains all numbers that appear exactly i times.

Example: For our frequency map above with array length 6:

buckets[0] = []
buckets[1] = [3]    // 3 appears 1 time
buckets[2] = [2]    // 2 appears 2 times
buckets[3] = [1]    // 1 appears 3 times
buckets[4] = []
buckets[5] = []
buckets[6] = []

Step 3: Collecting Results #

const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
  if (buckets[i].length > 0) {
    result.push(...buckets[i]);
  }
}
return result.slice(0, k);

We iterate from the highest frequency bucket down, collecting elements until we have k items. The slice(0, k) ensures we return exactly k elements in case a bucket has multiple elements.

Example: For k=2, starting from bucket 3:

bucket[3] has [1], add it: result = [1]
bucket[2] has [2], add it: result = [1, 2]
We have k=2 elements, stop
Return [1, 2]

Complexity Analysis #

Bucket Sort Approach #

Time Complexity: O(n)

Building frequency map: O(n)
Creating buckets: O(m) where m = unique elements ≤ n
Collecting results: O(n) worst case
Total: O(n)

Space Complexity: O(n)

Frequency map: O(m) ≤ O(n)
Buckets array: O(n)
Total: O(n)

Sorting Approach #

Time Complexity: O(n + m log m)

Building frequency map: O(n)
Sorting: O(m log m) where m = unique elements
In worst case (all unique): O(n log n)

Space Complexity: O(m)

For the frequency map and sortable array

Key Takeaways #

Bucket sort shines when value range is limited: Since frequency can’t exceed n, bucket sort is perfect here
Hash maps for counting: Building frequency maps is a common pattern for array problems
Trade-offs: Sorting is simpler to understand but slower; bucket sort is optimal but requires more thought
Constraint-driven design: The “better than O(n log n)” requirement directly leads to the bucket sort solution

Common Pitfalls #

Forgetting parseInt: When iterating object keys, they’re strings - convert back to numbers if needed
Off-by-one in bucket size: Frequency can be 0 to n, so we need n+1 buckets
Overcollecting: Always ensure you return exactly k elements, not more
Not handling duplicates in buckets: Use ... spread to add all elements from a bucket

This problem demonstrates the power of bucket sort when dealing with bounded integer frequencies and shows how understanding constraints can lead to optimal solutions.