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]

Option 1 - Map to count + Sort to get top k - O(nlgn)

- We need to count what is the freq or how many times an item appeared.
- The obvious thing is for each item put it in a hashmap where
- Key is the item
- Value is the number of times it appeared

- Now the only thing that is left is to sort this hashtable.
- sorting is O(nlgn), placing everyting and counting is O(n) so this makes it overall O(nlgn)

Option 2 - Improvement over option 1 - Instead of sorting use a Heap

- This is a common thing when you need to sort but the core of the problem is not sorting but as in this example only get top k then we could utilize a heap.
- We still build a map as in option 1 which takes O(n) this is the counting map.
- Building a heap heapify takes O(n)
- Remove each item from the heap is O(lg(n)) until we removed k items - as each pop from a heap is lg(n)
- Overall this makes it klg(n) + n which can be better than nlgn if k < n

Option 3 - O(n) - Use buckets for finding the top k

- Start as usual build a hashtable for counting how many times each item appears this would be O(n)
- Now create an array [] of size of number of items we have here
`index i`

would be a list of the number occuring`i`

times`[].get[7] --> [the items that appeared 7 times]`

- And as you see to get the top k we just need to traverse the top k elements of this list
- Overall this means O(n) for creating the hashtable and O(n) for traversing this buckets list.

Here is the actual implementation of the buckets solution:

```
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# step 1 - put it in the map
# [1,1,3,4] --> {
# {1 --> 2}
# , {3 --> 4}
# , {4 --> 1}
# }
#
# step 2 prepare buckets [0, ... nums.length ] -> a number can appear at most nums.
# Bonus - buckets already sorted by index last bucket is one with highest number if count.
#
# Step 3 Read buckets in reverse order.
appearances = {} # map {number -> # times appears }
for x in nums:
appearances[x] = 1 + appearances.get(x, 0)
buckets = [[] for i in range(len(nums) + 1)] # [] - An array of arrays, we are going to keep all the x that are in each bucket appeared number of times as index of bucket.
for (x, num_appearances) in appearances.items():
buckets[num_appearances].append(x)
res = []
for i in range(len(buckets) - 1, 0, -1):
for x in buckets[i]:
res.append(x)
if (len(res) == k):
return res;
```

## Comments

## Post a Comment