MediumLeetCode #347Arrays & Hashing

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Constraints

1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4, k is in the range [1, the number of unique elements]

Examples

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

Output: [1,2]

Solution

Approach

Count frequencies with hash map, then use bucket sort (index = frequency) or heap to find top k elements in O(n) time.

def topKFrequent(nums, k):
    count = Counter(nums)
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)
    result = []
    for i in range(len(bucket) - 1, 0, -1):
        for num in bucket[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Complexity

Time:O(n)

Space:O(n)

Hints

1.First count frequencies
2.Think about bucket sort where index is frequency
3.Alternatively use a min-heap of size k

Asked at

Google