L25. Merge K Sorted Lists | Multiple Approaches

Please do give us a like, and subscribe to us if you are new to our channel.

[abinash]

Great Explanation. Whenever I m having a issue in understanding an algorithm my first go-to person is you Striver. Thanks mate.

[tommyls]

Thanks for the explanation. In my solution, I just added all elements in the list in the PQ. Much easier to do, but I think the time complexity of that is:
(1) (n * k)log(n * k) [for the initial insert]
(2) (n * k)log(n * k) [for subsequent removes].
And space complexity is o(n*k).

[mountain_guest]

Hey Striver, can you add this question to the A2Z list? The feeling of clicking Done after solving the question is sublime :)
Edit: The problem is under heap section. The article and vid link aren't there, prolly since this is a recent video.

[moksh]

i want to seriously thank you i had doubts in this question but you made them crystal clear, love you bro

[swagcoder]

Great Explanation striver. Just one point! I think the Space Complexity of the most optimal approach is O(n*k) and not k. As at max all the elements (n*k) will be there in the priority queue!

[k.murari]

Hlo sir,
Please upload as much video as you can. I see you haven't uploaded much video in recent times. Please upload some more videos. Thank you 🙏

[ayushkumarprasad]

For better solution if we assume all k lists has N nodes so doesn't time complexity will be O(2nk) like in previous video where we use recursion and time complexity was O(2nm)

[shameekagarwal]

amazing job!! was preparing from a2z sheet

am i wrong when i say this -
i think when you build the initial heap for k elements, complexity is not O(k*logk), but just O(k)

while i haven't bothered looking at the theoretical proof, intuition might be -
when you insert 1st element, heap height is 1, not logk
when you insert 2nd and 3rd element, heap height is 2 and not logk
and so on...

[rushilvyas]

Why s the problem link opening Flatten a Linked List problem? Where is the problem link for Merge k Sorted Lists

[nishantsharma]

Why can't we do it in the same way as Flattening a Linked list like in the previous video? aren't these essentially the same question? we had k lists there as well?

[CocoPaw]

14:45 why space complexity is o(1), we are creating a list for storing linkedlists so it should be O(n1+n2+n3+n4) ??

[psionl]

I guess the C++ pq library doesn't have a "heapify" method. Otherwise, making a pq out of the lists could be done in O(k) instead of O(k log k) time.

[jritzeku]

Why cant we process all the sublists initially? And then pop all items and simply store them in our answer link list since minHeap will ensure smallest is removed. This seems more
intuitive and should have similar performance ...maybe even benefits because we're not having to bunch of if checks.




var mergeKLists = function (lists) {
// Create a min-heap using MinPriorityQueue with priority based on node value
const minHeap = new MinPriorityQueue({ priority: (item) => item.val });

// Add all nodes from all lists to the min-heap
for (let head of lists) {
while (head) {
minHeap.enqueue(head);
head = head.next;
}
}

// Create a temporary head for the merged list
const tempHead = new ListNode();
let curr = tempHead;

// Process the min-heap until it's empty
while (!minHeap.isEmpty()) {
// Dequeue the node with the smallest value
const { val, next } = minHeap.dequeue().element;
// Add the smallest node to the merged list
curr.next = new ListNode(val);
curr = curr.next;
}

// Return the merged list starting from the next of temporary head
return tempHead.next;
}

[adbhutakalpniya]

why this question while merging has TC of N^3 while in previous question flattening of linked list it is N*m, both questions are very similar and work on same idea. do help me

[pragati]

from where did you have learnt all these?

[wroxtaar]

this problems's notes are not present in you sheets. please upload.

[shomilmaurya]

Can we not make one big list from k-1 lists, and merge this list with kth list?
We will perform sort two list only at last with one big list obtained from appending k-1 lists and kth list. It will be better I think?

[abhaykumarsingh]

O(NlogK) and O(1) space soln(But there is Auxilary space for recursion call) using divide and conquer approach

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode Conqueror(ListNode head1, ListNode head2){
ListNode temp1=head1;
ListNode temp2=head2;
ListNode mergeLL=new ListNode(Integer.MIN_VALUE);
ListNode mergedPtr=mergeLL;
while(temp1 != null && temp2 !=null){
if(temp1.val <=temp2.val){
mergeLL.next=temp1;
temp1=temp1.next;
mergeLL=mergeLL.next;
}
else{
mergeLL.next=temp2;
temp2=temp2.next;
mergeLL=mergeLL.next;
}
}

while(temp1 != null){
mergeLL.next=temp1;
temp1=temp1.next;
mergeLL=mergeLL.next;
}
while(temp2 != null){
mergeLL.next=temp2;
temp2=temp2.next;
mergeLL=mergeLL.next;
}
return mergedPtr.next;
}
public ListNode Divide(ListNode[] lists, int start, int end){
//base condn
if(start >=end){
return lists[start];
}
int mid=(start+end)/2;
ListNode head1= Divide(lists, start, mid); //left
ListNode head2= Divide(lists, mid+1, end); //right

return Conqueror(head1, head2);

}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
return Divide(lists, 0, lists.length-1);
}
}

[aditorialme]

Is anybody else getting SIGBART error in test case 3

[navneetuppal]

Please can anyone tell why this convert array to LL code in brute force approach giving runtime error??
ListNode* head = new ListNode(arr[0]);
ListNode* temp = head;
for(int i = 1; i < arr.size(); i++) {
ListNode* newNode = new ListNode(arr[i]);
temp -> next = newNode;
temp = temp -> next;
}