# Top K Frequent Elements

##### December 20, 2023

## Problem #

Given an unsorted list of integers, find the k most frequent elements in the list. Return them as a list with each element’s frequency.

## Solution #

To solve the problem of finding the k most frequent elements in an unsorted list of integers, you can use a combination of a hash map (dictionary in Python) to store the frequency of each element and a heap to efficiently find the k most frequent elements. Here’s how you can do it in Python:

- Use a dictionary to count the frequency of each element in the list.
- Use a heap (priority queue) to keep track of the k most frequent elements.
- Convert the heap to a list and return it.

Here’s the implementation:

```
import heapq
from collections import Counter
def k_most_frequent(nums, k):
# Count the frequency of each element
freq = Counter(nums)
# Use a min-heap to find the k most frequent elements
# The heap will store pairs of (-frequency, element) to sort by frequency
min_heap = []
for num, count in freq.items():
heapq.heappush(min_heap, (-count, num))
if len(min_heap) > k:
heapq.heappop(min_heap)
# Extract the elements and their frequencies from the heap
result = [(-freq, num) for freq, num in min_heap]
return result
# Example usage
nums = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4]
k = 2
print(k_most_frequent(nums, k)) # Output will be the 2 most frequent elements along with their frequencies
```

In this code:

- The
`Counter`

class from the`collections`

module is used to count the frequency of each element in the list. - A min-heap is used to keep track of the k elements with the highest frequency. The heap stores tuples of the form
`(-frequency, element)`

so that the element with the lowest frequency (highest negative frequency) is always at the top of the heap. - The
`heapq`

module is used to efficiently manage the heap. - After pushing all elements to the heap and ensuring its size doesn’t exceed
`k`

, the top`k`

elements are retrieved. Their frequencies are negated back to positive values for the final result.