Leetcode: Top k frequent elements
Given a list nums
and a positive integer k
, return the top k
frequent items from the list. A time complexity constraint is not given for this task.
The task can be broken down into two problems. First, identifying the most frequent items and then returning them. For the first part, I used a simple map to count the occurrences. Afterwards, I iterated over the map and flipped the key
and value
around in a tuple. If for example the number 10
occurred 5
times, the corresponding tuple would be (5, 10)
. With this structure I was able to use the heapq
package in Python. This library uses the first element of a tuple to determine the order of elements. As his library creates by default a min heap and we are interested in the maximum elements, we can simply make the values negative. This puts the most frequent elements at the top of the heap.
Runtime: 227 ms, faster than 14.08% of Python3 online submissions for Top K Frequent Elements. Memory Usage: 18.7 MB, less than 71.72% of Python3 online submissions for Top K Frequent Elements.