Reference: LeetCode 347 / LeetCode 692
Difficulty: Medium

## Top K Frequent Elements

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

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.

Example:

### Heap

• Build a hash map val -> count. $O(N)$
• Build a min heap of size $k$. $O(N\log{k})$
• Build an output list. $O(k\log{k})$

Note:

• If we use max heap, the runtime would be $O(N\log{N})$, since we cannot keep the heap size as $k$. Therefore, for largest problems we use min heap.
• The resulting order is not required.

Time: $O(N\log{k})$
Space: $O(N)$

## Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example:

### Sorting

For comparator, from left to right: w1, w2 and count(w2), count(w1).

Time: $O(N\log{N})$
Space: $O(N)$

### Heap

Note: Be careful of the code in the comparator.

Time: $O(N\log{k})$
Space: $O(N)$

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.