Merge K Sorted Lists
Application of Heap Data Structure
Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Explanation: The linked-lists are:
[ 1->4->5, 1->3->4, 2->6 ]
merging them into one sorted list:
Input: lists = 
Input: lists = []
Prerequisite: Having very good knowledge of Heap data structure. Consider taking a look at the below chapters:
- Heap Fundamentals
- Heap: GetMax()/GetMin(), DeleteMax()/DeleteMin() and Insert()
- Heap Sort
- Priority Queue
This is not a very complex problem. If you find yourself having trouble coming up with the algorithm for this problem, you might first want to work on thinking more critically and systematically, while at the same time making sure that you are thinking in the right direction. What I am trying to say here is: your thinking process is super important for problem solving. Thinking logically and systematically, without getting overwhelmed with the magnitude of complexity of the given problem, is an art. So let's not worry about knowing advanced algorithms and data structures, because most solutions only need commonly used algorithms and data structures. Most complex looking problems have simple solutions. Below is how my thinking process would be if I see this problem for the first time:
Let's suppose we are given N lists. Now what is important to keep in mind is that
these lists are SORTED.
Since all the given lists are sorted, the lowest value in the merged list would be the lowest of
all the first elements of the given N lists.
Suppose, the first element of the mth list turns out to be the lowest.
Now our next objective is to find the second lowest element. Notice that the second lowest element would be the lowest of
the first elements of the (N - 1) lists which does not include mth list, because
first element of mth list is the first lowest element,
- the second element of the mth list.
- the first elements of the (N - 1) lists which does not include mth list, because first element of mth list is the first lowest element,
We repeat the above procedure until we have processed all the elements in N lists.
We simplify the above algorithm as below:
- So at any point of time, the next lowest element is the lowest of all the first elements of the N lists. Make the second element the first for the list which had the lowest first element. Repeat this until all the elements are processed for all the N lists.
So a big part of the solution is to be able to find lowest (or, minimum) of N elements efficiently. Which data structure would serve our purpose really good here ? Min heap. Retrieving min element from Min Heap is O(1). After every operation like Insertion and Deletion, min element always ends up at the root of the min heap. Insertion and Deletion operations are O(logn), where n = size of heap.
If we keep the first elements from all the lists in a min heap, the root of the min heap will have the min element. Once we remove min we insert the next node of the min node in the min heap.
Below is the implementation of the above algorithm using Min Heap.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Time Complexity:O(nlogn) + O(Klogn) = O(Klogn) since K > n.
Detailed time complexity analysis is given inline in the code above.
Senior SDE | Chief Architect
Microsoft | University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.