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:**

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

### 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.

1 | public List<Integer> topKFrequent(int[] nums, int k) { |

**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:**

1 | Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 |

### Sorting

For comparator, from left to right: `w1, w2`

and `count(w2), count(w1)`

.

1 | public List<String> topKFrequent(String[] words, int k) { |

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

### Heap

**Note:** Be careful of the code in the comparator.

1 | public List<String> topKFrequent(String[] words, int k) { |

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