Leetcode 347: Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. (This is Leetcode problem # 347)

Example:

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

Output: [1,2]

Explanation:

1 occurs three times and 2 occurs two times in the input. Those two elements are the top-2 frequent elements and hence the output is [1, 2].

Initial Thoughts

This is a good algorithmic problem. It not only helps in practicing my algorithm skills but also helps in mastering Go skills. In particular, I would like to solve it using heaps so as to develop some practical skills around heaps usage in Go. Note that this problem can also be solved in several other ways.

Before diving into the solution, it helps to understand a bit about what heaps are and what kind of support Go provides to work with heaps.

A heap is specialized tree structure that satisfies heap property. A heap property can be of type min-heap or max-heap. If each node is the minimum-valued node within its subtree, then it is called a min-heap. If each node is the maximum-valued node within its subtree, then its called a max-heap. Heaps have many applications. One such (very popular) application of heaps is Priority Queues.

Go provides a package called “heap” that defines an interface type called “Interface”. An interface in Go defines a set of methods (aka behaviors) and a concrete type can implement those methods to satisfy the requirements of that interface. What this essentially means is the following two things for our current purpose:

• Define a type called MinHeap
• And implement heap.Interface methods on MinHeap

With that covered, let us see a high level description of the solution organized into different steps.

• Step1: Build a map of element values to counts from the input array
• Step2: Build two arrays (or slices in Go) to hold values and their counts
• Step 3: Define a MinHeap type that satisfies heap.Interface
• Step 4: Build a min-heap using values and counts arrays
• Step 5: Construct final result by popping k elements from the min-heap

Steps 1 and 2 are fairly simple. Steps 3, 4 and 5 require understanding of how to implement heaps and work with them in Go. Let us see all these steps in action.

Step 1: Given a slice of nums, build a map of elements to counts. It is easy to code this part and the following gist shows how to do it

Step 2: Build values and counts arrays. It is fairly simple to code this part also. The following gist shows how to do this.

Step 3: Define a MinHeap type that satisfies heap.Interface

As I mentioned earlier, this step involves defining a custom data type and implementing methods on it so as to satisfy heap.Interface requirements. The following code snippet just shows how to do it.

Step 4: Build a min-heap using values and counts

We can now build a min-heap using values and counts slices constructed earlier. The following gist shows how to do this.

Step 5: Construct the final result

The min-heap now contains k elements. We can pop the heap k times or until the heap is empty and build an output slice which we can finally return to the parent function.

Thanks for reading and I hope you enjoyed this article.