> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-09-2022-347.md).

# 02/09/2022 347

Method: use a hashmap to get the frequency of each element in the array. Then use Min heap to store elements which are sorted by their frequencies. When the heap size is > k, then we poll the min elements until the size of the heap is k. Finally, add all the elements in the heap into an array.

Time O(nlogk)

Space O(N)

[@kylu](https://leetcode.com/kylu) This is only true because you're using a MinHeap. Python's implementation of heap is MinHeap, meaning any parent node must have a priority lesser than or equal to any of its descendant nodes (lower priorities at the top, higher priorities at the bottom). By doing that you do get a time complexity of O(n log(k)). The reason for this is that you can keep a heap of maximum size k, since every time you come across an entry in your map with a count higher than the current minimum (top element in your heap), you can safely remove it and replace it with the new, larger candidate. So, restoring the invariant in a heap of size k after replacing a node (or pop+push) is in the order of O(log(k)) time. Repeating this n times is O(n \* log(k)) as you said.

However, this is not true in the case of using a MaxHeap as mentioned by [@satwik95](https://leetcode.com/satwik95) . Using a MaxHeap you're stuck with O(n log(n)) time by pushing n values into the heap taking log(n) time each one to restore the heap invariant. Even if you wanted to lock the size of your MaxHeap to just k elements, which element would you remove at each iteration? The top element is going the max priority element now, and by removing it you could be discarding a very good candidate. Also, the last element (bottom-right in the tree) is not guaranteed to be the minimum. Getting the final result out of the heap is an additional O(k log(n)) operation that can be ignored in the overall time complexity since k is strictly less than or equal to n.

To improve this MaxHeap solution we could use a heapify function, also mentioned by [@satwik95](https://leetcode.com/satwik95) taking O(n) time to build the heap in-place in the given input array, and O(k log(n)) to remove the top k most frequent elements.

So, there's no way to get O(n log(k)) time using a MaxHeap, this is only possible using MinHeap, unless of course you negate the priorities which will essentially "convert a MaxHeap into a MinHeap" (or vice versa). [@lgibson](https://leetcode.com/lgibson)

class Solution { public int\[] topKFrequent(int\[] nums, int k) { // O(1) time if (k == nums.length) { return nums; }

```
    // 1. build hash map : character and how often it appears
    // O(N) time
    Map<Integer, Integer> count = new HashMap();
    for (int n: nums) {
      count.put(n, count.getOrDefault(n, 0) + 1);
    }

    // min heap : init heap 'the less frequent element first'
    Queue<Integer> heap = new PriorityQueue<>(
        (n1, n2) -> count.get(n1) - count.get(n2));

    // 2. keep k top frequent elements in the heap
    // O(N log k) < O(N log N) time
    for (int n: count.keySet()) {
      heap.add(n);
      if (heap.size() > k) heap.poll();    
    }

    // 3. build an output array
    // O(k log k) time
    int[] top = new int[k];
    for(int i = k - 1; i >= 0; --i) {
        top[i] = heap.poll();
    }
    return top;
}
```

}

Method 2:

Bucket sort

Use a hashmap to count the array's elements' frequencies. Create a list of empty lists for bucktes for frequencies. Noted the list size should be array's size + 1. Then iterate the hashmap's keyset,  add elements to corresponding frequency buckets. Finally take the `k` last elements from this list, these elements will be top K frequent elements.

Time O(n)

Space O(n + k)

class Solution { public int\[] topKFrequent(int\[] nums, int k) { Map\<Integer, Integer> counts = new HashMap<>();

```
for (int currNum : nums) 
    counts.put(currNum, counts.getOrDefault(currNum, 0) + 1);

// Number of occurrences of all elements must be in [0, nums.length].
List<Integer>[] buckets = new ArrayList[nums.length + 1];   
for (int key : counts.keySet()) {
    int freq = counts.get(key);
    if (buckets[freq] == null) 
        buckets[freq] = new ArrayList<>(); 
    buckets[freq].add(key);
}

int[] result = new int[k];        
int resIdx = 0;
for (int i = buckets.length - 1; i >= 0; i--) {
    // empty buckets are null values.
    if (buckets[i] == null) continue;  
    for (int currNum : buckets[i]) {
        result[resIdx++] = currNum;
        if (resIdx == result.length) return result;
    }
}
return result;
```

} }