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.
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).
I do not think your solution is easier since you are adding more elements as well as increasing the time complexity. You only need the minimum of all lists to find out the minimum of them to put forth in our required sorted list.
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?
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
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; }
space complexity for this approach will be equal to the total number of nodes which is too much.O(nxm) according to strivers approach we are limiting the size of priority queue to number of heads or the list size.O(n)
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)
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!
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...
I tried one solution and it looks like O(n*k) to me and expected time complexity is O(n*k*logk). However, I am getting TLE for my solution. Can someone please have a look and tell me if solution takes more time than what I am thinking and how? def mergeKLists(self,arr,K): # code here # return head of merged list temp=res_head=None ind=-1 for i in range(K): if not res_head or res_head.data>arr[i].data: res_head=temp=arr[i] ind=i arr[ind]=arr[ind].next
while True: a=None for i in range(K): if arr[i]: if not a or a.data>arr[i].data: a=arr[i] ind=i if a: temp.next=a temp=a arr[ind]=arr[ind].next else:break
return res_head Note: solution working fin for first 205 test cases and gives TLE for 206th test case in gfg
Why are we using greater int in pq, our pq is supposed to store smallest value node at top , so greater will make it in descending order like it does to vector
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?
yes bro u can make one big list from k-1 lists but that list won't be sorted if u just add elements linearly so let's analyse time complexity so first u will insert all the elements from k-1 lists so insertion would take place at time complexity of o(n*k) then , u would sort this big list suppose we use merge sort for it so time complexity would he o (n*klog(n*k) ) and now u will sort this sorted big list with the kth list so again time complexity would be o( n+ n*k ) where n is the size of kth list and n*k is size of the big list so overall time complexity is n*k + n*klog(n*k) + n +n*k
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; }
@navneetuppal9753, use the code below. Although, mine is in javascript but you can convert it to c++ function convertArrayToLinkList(array) { if (array.length === 0) return null; let head = new Node(array[0]); let mover = head; for (let i = 1; i < array.length; i++) { let temp = new Node(array[i]); mover.next = temp; mover = temp; } return head; }
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.
Its already there under HEAPS section-MEDIUM PROBLEMS
@@Kaurs_Life Oh yes! Thanks for pointing out.
Why s the problem link opening Flatten a Linked List problem? Where is the problem link for Merge k Sorted Lists
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).
I do not think your solution is easier since you are adding more elements as well as increasing the time complexity. You only need the minimum of all lists to find out the minimum of them to put forth in our required sorted list.
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?
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 🙏
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
In last question TC is O(m*n*n)
Sir done some mistake there..
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;
}
space complexity for this approach will be equal to the total number of nodes which is too much.O(nxm) according to strivers approach we are limiting the size of priority queue to number of heads or the list size.O(n)
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 =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);
}
}
i want to seriously thank you i had doubts in this question but you made them crystal clear , love you bro
public ListNode mergeKLists (ListNode []lists){
ListNode dummy =new ListNode (0);
ListNode cur=dummy;
Queuepq=new PriorityQueue((a,b)->a.val-b.val);
for(ListNode list:lists)
if(list!=null)
pq.offer(list);
while(!pq.isEmpty()){
ListNode temp=pq.poll();
if(temp.next!=null)
pq.offer(temp.next);
cur.next=temp;
cur=cur.next;
}
return dummy.next;
}
🎉❤
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)
Can someone tell me what will be the time complexity of my code 👇👇
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummyNode = new ListNode(-1);
ListNode* t1 = list1;
ListNode* t2 = list2;
ListNode* temp = dummyNode;
while(t1 != NULL and t2 != NULL){
if(t1->val val){
temp->next = t1;
t1 = t1->next;
}
else{
temp->next = t2;
t2 = t2->next;
}
temp = temp->next;
}
if(t1) temp->next = t1;
else temp->next = t2;
return dummyNode->next;
}
ListNode* mergeKLists(vector& lists) {
if (lists.size() == 0) return NULL;
if (lists.size() == 1) return lists[0];
ListNode* ll = mergeTwoLists(lists[0],lists[1]);
for(int i=2;i
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) ??
Great Explanation. Whenever I m having a issue in understanding an algorithm my first go-to person is you Striver. Thanks mate.
Thank you
@@rahulmandal4007 welcome
Is anybody else getting SIGBART error in test case 3
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!
Not true. Only the heads of the linked lists are in the priority queue.
at max means maximum amount of numbers at any given time, it will be equal to the number of heads (i.e the size of the vector that is k)
this problems's notes are not present in you sheets. please upload.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue pq = new PriorityQueue((a, b) -> a.getKey() - b.getKey());
for (int i = 0; i < lists.length; i++) {
if (lists[i]!= null) {
pq.add(new Pair(lists[i].val, lists[i]));
}
}
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
while (!pq.isEmpty()) {
Pair pair = pq.poll();
ListNode node = pair.getValue();
if (node.next != null) {
pq.add(new Pair(node.next.val, node.next));
}
temp.next = node;
temp = temp.next;
}
return dummyNode.next;
}
Anyone facing Run time error??
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...
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.
which drawing software are you using?
I tried one solution and it looks like O(n*k) to me and expected time complexity is O(n*k*logk). However, I am getting TLE for my solution. Can someone please have a look and tell me if solution takes more time than what I am thinking and how?
def mergeKLists(self,arr,K):
# code here
# return head of merged list
temp=res_head=None
ind=-1
for i in range(K):
if not res_head or res_head.data>arr[i].data:
res_head=temp=arr[i]
ind=i
arr[ind]=arr[ind].next
while True:
a=None
for i in range(K):
if arr[i]:
if not a or a.data>arr[i].data:
a=arr[i]
ind=i
if a:
temp.next=a
temp=a
arr[ind]=arr[ind].next
else:break
return res_head
Note: solution working fin for first 205 test cases and gives TLE for 206th test case in gfg
Aaj mein linked list merge kroon😅
Happy new year striver
Here is the discussed optimized CPP code :
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if(lists.size() == 0) return NULL;
priority_queuepq;
for(int i = 0 ; i < lists.size() ; i++){
if(lists[i]){
pq.push({lists[i]->val,lists[i]});
}
}
ListNode* dummyNode = new ListNode(-1);
ListNode* temp = dummyNode;
while(!pq.empty()){
pairp = pq.top();
temp->next = p.second;
pq.pop();
if(p.second->next){
pq.push({p.second->next->val,p.second->next});
}
temp = temp->next;
}
return dummyNode->next;
}
};
Thank you Striver ❤
Why are we using greater int in pq, our pq is supposed to store smallest value node at top , so greater will make it in descending order like it does to vector
Understood 😃
from where did you have learnt all these?
done and dusted
UNDERSTOOD;
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?
yes bro
u can make one big list from k-1 lists
but that list won't be sorted if u just add elements linearly
so let's analyse time complexity
so first u will insert all the elements from k-1 lists
so insertion would take place at time complexity of o(n*k)
then , u would sort this big list
suppose we use merge sort for it
so time complexity would he
o (n*klog(n*k) )
and now u will sort this sorted big list with the kth list
so again time complexity would be
o( n+ n*k ) where n is the size of kth list and n*k is size of the big list
so overall time complexity is
n*k + n*klog(n*k) + n +n*k
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;
}
@navneetuppal9753, use the code below. Although, mine is in javascript but you can convert it to c++
function convertArrayToLinkList(array) {
if (array.length === 0) return null;
let head = new Node(array[0]);
let mover = head;
for (let i = 1; i < array.length; i++) {
let temp = new Node(array[i]);
mover.next = temp;
mover = temp;
}
return head;
}
@@adebisisheriff159 Here is a code for burte force :
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
vector arr;
for(int i=0;ival);
temp=temp->next;
}
}
sort(arr.begin(),arr.end());
ListNode *head=new ListNode(-1);
ListNode * tail=head;
for(int i=0;inext=n;
tail=n;
}
return head->next;
}
};
check your constructors
check after changing it in following :
temp->next = new Node(arr[i]);
temp = temp->next;
return head;
100% understood striver
understood
Understood
god
seriously great work!
US
understood
thank you
Thank you very much
Understood✅🔥🔥
Understood
Thanks