Using Heaps and Dictionaries for top frequent k elements.

Let's start with the problem:

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

Here are some example inputs and expected outputs:

# Example 1
Input: nums = [1,1,1,2,2,30, k = 2
Output: [1,2]

# Example 2
Input: nums = [1], k = 1
Output: [1]
Copy

Anytime we need to count something that tells use a dictionary is perfect to use for this.

First step we need to loop through the list in nums and count how many times they occur. Next we need to the top k elements.

To do this we first count the elements:

Copy

Step 2 is we need to count the top k elements, this is where we can use a heap.

We use a heap, which is a tree data structure where the lowest value is on top (or at the root of the tree), and all values that comes after increase as you go down. Heaps will automatically maintain the structure as we add and remove things from it, it will reorder the structure to maintain this order.

A cool trick we can use to store more than one value in the heap is to use a tuple. (Since we need to keep track of the counts, but at the end we need to return the actual number, no the count)

The heap will use the first value in the tuple to heapify, which is perfect for this use case.

Copy

and putting it all together:

Copy