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:

• Output:

• 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.

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.

Rust Solution

BinaryHeap is a max-heap, so wrapping each (usize, i32) in Reverse inverts the ordering into a min-heap — the least-frequent pair sits on top and heap.pop() evicts it once heap.len() exceeds k. Counting uses the entry API: *freq.entry(*n).or_insert(0) += 1 hands back a mutable reference to the slot (inserting 0 first if the key is absent) instead of a second lookup, and for n in &nums borrows the vector so it survives the loop. Ordering the tuple as (f, num) puts frequency in the primary comparison slot, and the final heap.into_iter().map(|Reverse((_, n))| n).collect() destructures the Reverse wrapper in the closure's pattern to recover just the numbers.

Go Solution

container/heap ships only the algorithms, so PQ must satisfy the interface itself: Len/Less/Swap on value receivers plus Push/Pop on the pointer receiver *PQ, which reslice *p to grow and shrink the backing array. Less comparing p[i].freq < p[j].freq makes it a min-heap, and because the pre-generics API is untyped, every element round-trips through interface{}, forcing the x.(Item) and heap.Pop(pq).(Item).num type assertions. Counting leans on the map zero value — freq[n]++ on a make(map[int]int) needs no comma-ok check, since a missing key already reads as 0.