Ace Your Coding Interview — Blind 75 Solved and Explained — Part 8 Heaps

6 min readDec 11, 2022

This week we are going to shift our focus to heaps. A heap is a particular type of tree-based data structure with certain characteristics. The unique part of heaps is that the root will always be the largest or smallest element and the tree will adjust itself when this node is removed to have a new root with those characteristics.

I will attach a link from geeks for geeks that best explains the intricacies of how heaps function.

Heap Data Structure - GeeksforGeeks

www.geeksforgeeks.org

Another point to make before starting these questions is that even though we solve them by utilizing heaps, there are many other ways to approach a reasonable solution that are more efficient and faster. However, to focus on solving a few questions using heaps, we are going to utilize heaps in this section.

Blind 75 LeetCode Questions - LeetCode Discuss

leetcode.com

Question 1 — Find Median from Data Stream

Find Median from Data Stream - LeetCode

leetcode.com

Solution for Find Median from Data Stream

This question becomes one of the easier ones on the list once you figure out the main approach. The best way to approach a solution is by utilizing not one but two heaps. One to work as a max heap and one as a min-heap. What we come to realize is the largest number in the bottom half of the list and the smallest number in the top half of the list can be utilized to find the median.

Our Approach:

Let’s start by creating two heaps — a max and a min heap. This is done by establishing two priority queues, one of which needs to be set up in reverse order. The reason for creating a min and a max heap is so that when peeking at the two heaps separately, we get the max from the bottom half and the min from the top half.
We make a method so we can add values into our separate heaps accordingly. We start by adding the value to our max heap and follow this by balancing out the min and max heap. How does this balancing occur? We move the largest element from the max heap to the min heap when necessary. If the size of the two heaps doesn’t match after this operation, move the smallest element from the min to the max heap to restore balance.
Our find median method is relatively straightforward at this point. All the complicated work is done. If the length of max and min heaps don’t match, we simply return the largest element of the max heap as it will be representing the median value. If the two heaps are equal in length this means the largest number from the max heap and the smallest number from the min heap can be added and divided by two to get the average. Due to the design of our heaps, this operation can be done by polling both heaps to get the according numbers.

Question 2- Merge K-Sorted-Lists

Merge k Sorted Lists - LeetCode

leetcode.com

This question uses some of our knowledge from the previous linked list section in combination with heaps to achieve a working solution. Questions that incorporate multiple topics like this are great to practice as it helps you practice skills from both topics simultaneously.

Our Approach:

To generate our heap we create a priority queue. We need to identify how our priority queue will be sorting the nodes. To accomplish we use a lambda expression that checks the value difference between two elements as a driving factor.
We need two nodes to accomplish our goal — one node for traversal and one to serve as our result. After creating these two nodes which we will use to sort our lists, we loop through all the available lists to our heap. At this moment our heap contains all the necessary lists, however, it is yet to be sorted.
Now, we can go into our heap and place nodes onto our result node until our heap is empty. This is where our traversal node comes into play. We retrieve the top heap element and assign it to a temporary node. This creates a cache-like scenario where the element we need can be accessed directly through this temp node rather than the heap itself.
Next, we point our traversal node to the temporary node and push the traversal node forward.
We need to add our next element back into the heap to restore the list we have taken out. So as you can see here, whenever we deal with a list we take out the necessary piece insert it into our root to complete, and return the list to the heap to poll from next time. So, if the next item in the list is not null add it back into the heap to be used for the next iteration.
After the heap is empty it means we have exhausted all the nodes in every list. We can return our sorted list.

Question 3 — Top K-Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

The approach we took for this problem utilizes a HashMap to create key value relationships and a heap that is sorted by the value of the HashMap. As I discussed in the introduction there are many other ways to solve this problem more efficiently and faster, however, for the sake of staying on the topic a heap is being utilized in our solution. Check out this solution below to see an alternative way to approach the question.

Alternative Solution:

Our Approach:

Create a HashMap that used to store integer values and their frequencies
Add all the numbers from the array into the HashMap if the number is already in the HashMap update frequency accordingly.
Create a heap by utilizing a priority queue. Use the value in the HashMap as the determining filter when adding into the heap.
Add all the key values from the HashMap into the heap. Since we have already identified the sorting when the priority queue was initialized when items are added they are already going to be ordered in what we need them to be.
Since they are already in the order we need them to be in. We can finish this problem by polling all the elements from the heap and adding them into an array.