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()