🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

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.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:

[
  1->4->5,
  1->3->4,
  2->6
]

merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Solution:

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()
• Heapify
• 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 m^th 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 m^th list, because first element of m^th list is the first lowest element,
    
  • the second element of the m^th list.

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.


Login to Access Content

Time Complexity:

O(nlogn) + O(Klogn) = O(Klogn) since K > n.
Detailed time complexity analysis is given inline in the code above.

Instructor: