Solving Top K Frequent Elements: Identifying Most Common Items

The "Top K Frequent Elements" problem involves identifying the most commonly occurring elements in an array. This challenge is about efficiently finding the elements that appear most frequently.

Problem Statement

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

Example

• Input:

((nums = [1, 1, 1, 2, 2, 3]), (k = 2));

• Output:

[1, 2];

• Explanation: The two most frequent elements are 1 and 2, which both appear three and two times respectively.

Solution Approach - Heap and Hash Map

The solution involves using a hash map to count the frequency of each element and then using a heap to efficiently extract the k most frequent elements.

function topKFrequent(nums: number[], k: number): number[] {
  const frequencyMap: { [key: number]: number } = {};
  for (const num of nums) {
    frequencyMap[num] = (frequencyMap[num] || 0) + 1;
  }

  const minHeap = new MinHeap<number>((a, b) => frequencyMap[a] - frequencyMap[b]);
  Object.keys(frequencyMap).forEach((num) => {
    minHeap.insert(parseInt(num));
    if (minHeap.size() > k) {
      minHeap.extract();
    }
  });

  return minHeap.getItems();
}

Breaking Down the Solution

• Frequency Count: Use a hash map to count the occurrences of each number.
• Min Heap: A min heap is used to keep track of the top k frequent elements.
• Heap Operations: Insert each number into the heap. If the heap size exceeds k, remove the smallest element (based on frequency).
• Result: The contents of the heap represent the top k frequent elements.

Conclusion

The Top K Frequent Elements problem is a great example of combining data structures - hash maps for frequency counting and heaps for efficient element retrieval - to solve a common algorithmic challenge.