Problem

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

Example 2:

Input: nums = , k = 1 Output: 

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Thought Process and White Board

• Use a hash-table to count the frequency of each number
• Sort the hash-table
• Return the top k elements by value

Code

class Solution:
def _create_ht(self, nums):
ht = {}
for num in nums:
if num in ht:
ht[num] += 1
else:
ht[num] = 1
return ht

def _ord_dict_val(self, my_dict, k):
ord_tuples = sorted([(v,k) for (k,v) in my_dict.items()], reverse=True)[:k]
return {k:v for (v,k) in ord_tuples}

def topKFrequent(self, nums, k):

ht = self._create_ht(nums)
if k < 0 or k > len(ht):
return -1
ord_dict = self._ord_dict_val(ht, k)

return ord_dict.keys()

Optimize

As shown in the output, the submission was accepted but it's outperformed by most submissions. The reason is because sorting has a complexity of O(nlogn). An improved solution would be:
• create a priority queue of k elements
• if the current element has a higher count than the min element in the queue, then replace the min element in the queue with the current element
• finally, the queue will have the top k freq elements
• The complexity is O(nlogk), n is len(nums), k is the count of result, it would be smaller than O(nlogn)