> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/arrays #concepts/programming/heap #concepts/programming/algorithms/bucket-sort]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/top-k-frequent-elements/]
> [up:: [[Leetcode MOC]]]
## Problem
Given an integer array `nums` and an integer `k`, return _the_ `k` _most frequent elements_. You may return the answer in **any order**.
**Example 1:**
**Input:** nums = [1,1,1,2,2,3], k = 2
**Output:** [1,2]
**Example 2:**
**Input:** nums = [1], k = 1
**Output:** [1]
**Constraints:**
- `1 <= nums.length <= 105`
- `-104 <= nums[i] <= 104`
- `k` is in the range `[1, the number of unique elements in the array]`.
- It is **guaranteed** that the answer is **unique**.
**Follow up:** Your algorithm's time complexity must be better than `O(n log n)`, where n is the array's size.
## Solution
### Mine
#### Python
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == len(set(nums)):
return list(set(nums))
counts = defaultdict(int)
freq_list = [[] for _ in range(len(nums))]
for num in nums:
counts[num] += 1
for num, freq in counts.items():
freq_list[freq].append(num)
res = []
reverse_iterator = len(freq_list) - 1
print(f"{freq_list=}")
while k != 0 and reverse_iterator >= 0:
if freq_list[reverse_iterator]:
res.append(freq_list[reverse_iterator].pop())
k -= 1
else:
reverse_iterator -= 1
return res
```
This can be improved by using a heap, which has a worst-case time complexity of $O(n\space log \space n)$.
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if k == len(set(nums)):
return list(set(nums))
counts = defaultdict(int)
for num in nums:
counts[num] += 1
# heap is a minheap, so we negate the values we're interested in
tups = [(-freq, num) for num, freq in counts.items()]
heapq.heapify(tups)
return [tups.pop()[1] for _ in range(k)]
```
#### Rust
### Neetcode
```python
class Solution:
def topKFrequenct(...):
count = {}
freq = [[] for i in range(len(nums)+1)]
for n in nums:
count[n] = 1 + count.get(n, 0)
for n, c in count.items():
freq[c].append(n)
res = []
for i in range(len(freq) -1, 0 -1):
for n in freq[i]:
res.append(n)
if len(res) == k:
return res
```
## Things I Learned
### Neetcode
Brute force $O(n\:log\:n)$ method would be to get num-frequency pairs and then sort by ascending order of frequency. But because you want top k, you can use a max heap.
Making the heap is $O(n)$ and popping from it `k` times is $O(k \cdot log \: n)$.
You can do even better than that, though, in $O(n)$ time. This uses an algorithm called [[bucket sort]].
In bucket sort, you maintain a list where the index represents the number, and the value represents the frequency. Because the values are unbounded and because it doesn't help us get the top `k` most frequent, this form of bucket sort isn't exactly useful.
But there's another way to do bucket sort. The index can instead represent the count and therefore the largest the array can be is the length of the input array, and the value is a list of all numbers that have that frequency.
For top k, we start at the end of the list, if nothing, skip it, if we get to a list, you can add as many items to it as satisfies the number k and then move on if still needed.
## Scratchpad
If `k` is equal to the length of `set(nums)` (total uniques), just return the unique values of `nums` by turning the list into a set and then back into a list. This is an edge case