Top K Frequent Elements: Multiple Solutions and Complexity Analysis

Introduction to Top K Frequent Elements

The "Top K Frequent Elements" problem is a classic algorithmic challenge that appears frequently in coding interviews and real-world data processing tasks. Given an array of elements and an integer k, the goal is to return the k most frequent elements in the array. While the problem statement sounds simple, it opens the door to several elegant solutions, each with distinct trade-offs in time and space complexity.

Understanding this problem deeply matters because it touches on fundamental concepts such as hash maps, heaps, bucket sort, and the quickselect algorithm. Mastering these approaches equips you with reusable techniques that apply to recommendation systems, log analysis, search ranking, and anomaly detection.

Problem Statement

Given a non-empty array of integers nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique.

For example, given nums = [1,1,1,2,2,3] and k = 2, the output should be [1,2] because element 1 appears three times and element 2 appears twice, making them the two most frequent elements.

Why It Matters

Beyond interview preparation, the Top K Frequent pattern shows up in many production scenarios:

• Search ranking: Returning the top k most relevant documents for a query.
• Log analysis: Identifying the most common error codes or IP addresses in server logs.
• Recommendation systems: Surfacing the most popular items to users.
• Network monitoring: Detecting the most active hosts or traffic sources.
• Natural language processing: Finding the most common tokens in a corpus.

In each of these cases, you need an efficient way to rank items by frequency and extract the top few. The choice of algorithm can dramatically affect performance, especially when the dataset is large.

Solution 1: Hash Map and Sorting

The most intuitive approach is to count frequencies using a hash map, then sort the entries by frequency and take the top k. This solution is easy to write and reason about, making it a great starting point.

Algorithm

• Build a frequency map by iterating through nums.
• Convert the map into a list of entries.
• Sort the entries in descending order by frequency.
• Return the first k keys.

Code Example

function topKFrequentSort(nums, k) {
  const freqMap = new Map();

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

  // Step 2: Convert to array of [num, freq] pairs
  const entries = Array.from(freqMap.entries());

  // Step 3: Sort by frequency descending
  entries.sort((a, b) => b[1] - a[1]);

  // Step 4: Extract top k keys
  return entries.slice(0, k).map(entry => entry[0]);
}

// Example usage
console.log(topKFrequentSort([1, 1, 1, 2, 2, 3], 2)); // [1, 2]

Complexity Analysis

Let n be the number of elements in nums and m be the number of unique elements.

• Time complexity: O(n + m log m). Building the map takes O(n), and sorting the unique entries takes O(m log m). In the worst case where all elements are unique, this becomes O(n log n).
• Space complexity: O(m) for the frequency map and the sorted list.

This solution is acceptable when n is moderate, but the sorting step is wasteful when k is much smaller than m, since we only need the top few elements rather than a full ordering.

Solution 2: Min-Heap of Size K

To avoid sorting all unique elements, we can maintain a min-heap of size k. As we iterate through the frequency map, we push entries into the heap. When the heap exceeds size k, we remove the smallest frequency. At the end, the heap contains exactly the top k frequent elements.

Algorithm

• Build a frequency map from nums.
• Initialize an empty min-heap that orders entries by frequency.
• For each entry, push it onto the heap. If the heap size exceeds k, pop the minimum.
• Extract the remaining k entries from the heap.

Code Example

function topKFrequentHeap(nums, k) {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // Min-heap simulation using an array with manual ordering
  // In production, use a proper priority queue library
  const heap = [];

  function heapPush(entry) {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[parent][1] > heap[i][1]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else break;
    }
  }

  function heapPop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n = heap.length;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < n && heap[left][1] < heap[smallest][1]) smallest = left;
        if (right < n && heap[right][1] < heap[smallest][1]) smallest = right;
        if (smallest !== i) {
          [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
          i = smallest;
        } else break;
      }
    }
    return top;
  }

  for (const entry of freqMap.entries()) {
    heapPush(entry);
    if (heap.length > k) {
      heapPop();
    }
  }

  return heap.map(entry => entry[0]);
}

console.log(topKFrequentHeap([1, 1, 1, 2, 2, 3], 2)); // [1, 2]

Complexity Analysis

• Time complexity: O(n + m log k). Building the map is O(n). Each of the m heap operations costs O(log k), giving O(m log k) total. When k is small relative to m, this is a significant improvement over sorting.
• Space complexity: O(m + k) for the frequency map and the heap.

The heap solution shines when k is small and m is large, which is the common case in practice. For example, finding the top 10 most frequent queries among millions of unique queries benefits enormously from this approach.

Solution 3: Bucket Sort

Bucket sort offers an elegant linear-time solution by exploiting the fact that frequencies are bounded by n. We create an array of buckets where the index represents a frequency, and each bucket holds the elements that occur with that frequency. We then iterate from the highest frequency bucket downward, collecting elements until we have k of them.

Algorithm

• Build a frequency map from nums.
• Create an array of n + 1 empty buckets.
• For each entry in the map, place the element in the bucket indexed by its frequency.
• Traverse buckets from highest index to lowest, collecting elements until k are gathered.

Code Example

function topKFrequentBucket(nums, k) {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  // Buckets indexed by frequency (0 to n)
  const buckets = Array.from({ length: nums.length + 1 }, () => []);

  for (const [num, freq] of freqMap.entries()) {
    buckets[freq].push(num);
  }

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

  return result;
}

console.log(topKFrequentBucket([1, 1, 1, 2, 2, 3], 2)); // [1, 2]

Complexity Analysis

• Time complexity: O(n). Building the map, populating buckets, and collecting results each take linear time.
• Space complexity: O(n) for the frequency map and the bucket array.

Bucket sort is the optimal solution for this problem in terms of asymptotic time complexity. However, it requires O(n) extra space for the buckets, which can be significant when n is very large but k is small.

Solution 4: Quickselect

Quickselect is a selection algorithm related to quicksort that can find the k-th largest element in average linear time. By applying quickselect to the array of unique elements ordered by frequency, we can partition the array so that the top k frequent elements end up on one side.

Algorithm

• Build a frequency map and convert it to an array of entries.
• Use quickselect to partially sort the array so that the k most frequent elements are in the first k positions.
• Return the keys of those first k entries.

Code Example

function topKFrequentQuickselect(nums, k) {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  const entries = Array.from(freqMap.entries());

  function partition(left, right, pivotIndex) {
    const pivotFreq = entries[pivotIndex][1];
    [entries[pivotIndex], entries[right]] = [entries[right], entries[pivotIndex]];
    let storeIndex = left;
    for (let i = left; i < right; i++) {
      if (entries[i][1] > pivotFreq) {
        [entries[storeIndex], entries[i]] = [entries[i], entries[storeIndex]];
        storeIndex++;
      }
    }
    [entries[right], entries[storeIndex]] = [entries[storeIndex], entries[right]];
    return storeIndex;
  }

  function quickselect(left, right, kSmallest) {
    if (left === right) return;
    const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
    const newPivot = partition(left, right, pivotIndex);
    if (kSmallest === newPivot) return;
    else if (kSmallest < newPivot) quickselect(left, newPivot - 1, kSmallest);
    else quickselect(newPivot + 1, right, kSmallest);
  }

  quickselect(0, entries.length - 1, k);
  return entries.slice(0, k).map(entry => entry[0]);
}

console.log(topKFrequentQuickselect([1, 1, 1, 2, 2, 3], 2)); // [1, 2]

Complexity Analysis

• Time complexity: O(n) average case, O(n^2) worst case. The worst case occurs with poor pivot choices, but randomizing the pivot makes the worst case extremely unlikely.
• Space complexity: O(m) for the entries array, plus O(log m) recursion stack in the average case.

Quickselect is attractive when you want average linear time without the O(n) space overhead of bucket sort. However, the worst-case quadratic time can be a concern in adversarial scenarios, so many implementations use a median-of-medians pivot strategy to guarantee linear time at the cost of higher constant factors.

Comparing the Solutions

Each solution has its own strengths and weaknesses. The table below summarizes the trade-offs:

• Sorting: Simplest to implement. Best when m is small or when you already need a fully sorted result.
• Min-heap: Best when k is much smaller than m. Ideal for streaming scenarios where you process elements one at a time.
• Bucket sort: Optimal linear time. Best when n is manageable and you want guaranteed performance.
• Quickselect: Average linear time with lower space overhead than bucket sort. Best when you want speed but cannot afford the bucket array.

Best Practices

When implementing Top K Frequent in production code, keep the following best practices in mind:

• Choose the right algorithm for your data: If k is tiny and m is huge, use a heap. If you need guaranteed linear time and can afford the space, use bucket sort.
• Handle edge cases: Always validate inputs. Check for empty arrays, k larger than the number of unique elements, and null values.
• Use library data structures: In production, prefer a tested priority queue implementation over a hand-rolled heap to avoid subtle bugs.
• Consider streaming variants: If data arrives continuously, maintain a running frequency map and a heap rather than recomputing from scratch.
• Profile before optimizing: The simplest solution is often fast enough. Only reach for bucket sort or quickselect when profiling shows the sort-based approach is a bottleneck.
• Be mindful of ties: The problem guarantees a unique answer, but real-world data often has ties. Decide on a deterministic tie-breaking strategy to ensure reproducible results.

Streaming Extension

In many real applications, data is not available all at once. You may need to find the top k frequent elements in a stream where you cannot store every element. A common approach combines a frequency sketch like Count-Min Sketch with a min-heap. The sketch provides approximate frequencies with bounded memory, and the heap tracks the current top k candidates.

class TopKStream {
  constructor(k) {
    this.k = k;
    this.freqMap = new Map();
    this.heap = [];
  }

  add(element) {
    const newFreq = (this.freqMap.get(element) || 0) + 1;
    this.freqMap.set(element, newFreq);

    // Update heap: remove element if present, re-add with new frequency
    const idx = this.heap.findIndex(e => e[0] === element);
    if (idx !== -1) this.heap.splice(idx, 1);

    this.heap.push([element, newFreq]);
    this.heap.sort((a, b) => a[1] - b[1]);

    if (this.heap.length > this.k) {
      this.heap.shift();
    }
  }

  topK() {
    return this.heap.map(e => e[0]);
  }
}

const stream = new TopKStream(2);
[1, 1, 1, 2, 2, 3].forEach(n => stream.add(n));
console.log(stream.topK()); // [1, 2]

Note that the simple streaming version above uses a linear search and sort for clarity. For production performance, replace these with a proper indexed priority queue or a combination of a hash map and a heap that supports efficient updates.

Conclusion

The Top K Frequent Elements problem is a microcosm of algorithm design, illustrating how different data structures and strategies trade off time, space, and implementation complexity. The sorting approach is the most readable, the heap approach excels when k is small, bucket sort delivers guaranteed linear time, and quickselect offers average linear time with lower space overhead. By understanding all four solutions and their complexity profiles, you can confidently choose the right tool for any variant of this problem, whether you are processing a static array, a high-volume stream, or a distributed dataset. The key is to match the algorithm to the shape of your data and the constraints of your system, always validating with real-world benchmarks before committing to an optimization.