LeetCode #347 Top K Frequent Elements

Medium

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.

Solution

Use a hash map to save counts of all numbers and use a heap to get k largest numbers out.

Complexity

It takes O(n)/O(nlogn) time to count numbers and insert into hash map in average/worst cases. Then, it takes O(n) time to build the heap and O(klogn) time to pop k largest elements. Therefore, its time complexity is O(n + n + klogn)/O(nlogn + n + klogn) = O(n + klogn)/O((n + k) logn) in average/worst cases.

For space complexity, it uses O(n) extra space for the hash map and O(n) for the heap. Thus, its space complexity is O(n + n) = O(n).