347. Top K Frequent Elements

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 = [1], k = 1 Output: [1]

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)