A small optimization I prefer in the merge function: in the while loop instead check (if l1 && l2) this will keep merging the two lists while both have items. Then afterwards we know that one of the lists could still have items. Append all the items with something like result.next = l1 || l2
You Awesome bro. not only you would solve the problem. Also with Time and space complexity. Most of the TH-camrs would not give interest in these complexities. Please keep posted videos. Do not stop bro. if possible post more than 1 video in a week
Thanks for the video, you explained it really well. I am a bit confused about final time complexity. It's log k levels, yes, but on every level the list size doubles, so we still have to go through all of the elements every time. Say, we have 4 lists, each n long; at the bottom we do 2 merges, of length 2n each, that's 4n elements to look at. At the top, we now merge these two lists, each is 2n long, so we have to go thru 4n elements (again). Overall we've looked at the elements 8n times, which is O(nk), not O(n log(k)). It would be faster (only 4n times) if we simply merged the lists sequentially. How are we benefiting from divide and conquer here? I am probably missing something here, would appreciate any comments.
Great video. One minor thing though, we don't really need l2 = l2.next or l1 = l1.next in line 31 and line 34 right, we can just break out of the loop and not worry about them since the remaining of them are already sorted in a linkedlist?
Thank you for your excellent explanation. Just one question, may I ask if space is O(1) or O(k)? I saw leetcode solution with O(1) space for this divide and conquer approach.
The space complexity for the recursive solution is O(k) where k is the recursion depth. The leetcode solution goes over the iterative approach which is O(1) space complexity. I went over the recursive approach because it is much easier to understand in my opinion :)
Do you think there is a way to solve this with a minHeap and still have a time complexity of nlogk? I have been able to solve it in nlogn time but I have had a few follow up questions with amazon/facebook where they ask how would you optimize your solution using a minHeap to a time complexity of nlogk Btw your videos are awesome, just subscribed.
At the moment you might be iterating over every node in every list and putting them all into the heap. This means your heap space will be O(N) and the the time to insert and remove from the heap will be O(logN) (because you have N items in the heap). Instead you can keep only k elements in the heap at one time. This will reduce the space to O(k) and the insert/remove time to O(logk) Initially put only the heads of each list into the queue. Then when removing from your heap, check if the node you dequeued has a next node. If so enqueue that to the heap
why didnt you just fill a list by traversing every single node of the list of listnode and then sort it using collection.sort and then create node from that sorted list ?
A small optimization I prefer in the merge function: in the while loop instead check (if l1 && l2) this will keep merging the two lists while both have items. Then afterwards we know that one of the lists could still have items. Append all the items with something like result.next = l1 || l2
Ah very cool optimization, thank for sharing
One of the best explanations w/ Divide and Conquer I've seen for this problem, thank you!
You're very welcome!
I just did Merge sort in college, this video explained it so well!!
Awesome, glad to hear that!
Thanks so much. Really like your video and the way you explain these problems. It is clear, detailed and easy to understand :)
Great to hear!
Awesome!! Nicely explained. Asked in a lot of companies
Thank you very much! It is definitely a useful problem to learn
@@AlgosWithMichael also your videos def helped me crack couple of Fangs! Please do let me know if you would like any contacts/ more info.
Happy to see after long time....
Thanks!!!
Most welcome 😊
Dude, I got tell ya this tutorial is high class.
Hahah thanks man, appreciate it!
Thanks Michael, you've explained the logic really well! subscribed :)
Glad it was helpful!
Clear and concise. Thank you!
Michael I had no idea you had a leetcode channel this is amazing I wish I knew about it before I did the grind this fall
Subscribed :)
Lol thanks man! Only a couple people at work know haha
✊
Awesome video man!! Amazing explanation
Appreciate it, more videos to come!
Great explanation as always!!!
Glad you liked it!
I like yours videos man. Thank you so much for the fantastic material
Thank you, glad I could help!
Great explanation man!!
Thank you!
You Awesome bro. not only you would solve the problem. Also with Time and space complexity. Most of the TH-camrs would not give interest in these complexities. Please keep posted videos. Do not stop bro. if possible post more than 1 video in a week
Thank you very much! And I'm trying to get more videos out, working a full time job cuts into most of the TH-cam time :/
Thanks for the video, you explained it really well. I am a bit confused about final time complexity. It's log k levels, yes, but on every level the list size doubles, so we still have to go through all of the elements every time.
Say, we have 4 lists, each n long; at the bottom we do 2 merges, of length 2n each, that's 4n elements to look at. At the top, we now merge these two lists, each is 2n long, so we have to go thru 4n elements (again). Overall we've looked at the elements 8n times, which is O(nk), not O(n log(k)).
It would be faster (only 4n times) if we simply merged the lists sequentially. How are we benefiting from divide and conquer here?
I am probably missing something here, would appreciate any comments.
here N means total elements of all k lists which is n*k
I love this where you did not use a Queue.
Haha yea I love this approach as well
Great video. One minor thing though, we don't really need l2 = l2.next or l1 = l1.next in line 31 and line 34 right, we can just break out of the loop and not worry about them since the remaining of them are already sorted in a linkedlist?
good explanation :) Thumbs up! 👍
Awesome thanks!
In the description u have written space complexity is O(LOGK) and in the video u said it’s O(K) , the correct answer is logK right ?
Woops yea
@@AlgosWithMichael nice , btw thanks for the clean explanation
anyime!
Thank you for your excellent explanation. Just one question, may I ask if space is O(1) or O(k)? I saw leetcode solution with O(1) space for this divide and conquer approach.
The space complexity for the recursive solution is O(k) where k is the recursion depth. The leetcode solution goes over the iterative approach which is O(1) space complexity. I went over the recursive approach because it is much easier to understand in my opinion :)
@@AlgosWithMichael Oh I got it. Thanks a lot Michael!
No problem!
i believe time complexity is O(n*klogk)
Do you think there is a way to solve this with a minHeap and still have a time complexity of nlogk? I have been able to solve it in nlogn time but I have had a few follow up questions with amazon/facebook where they ask how would you optimize your solution using a minHeap to a time complexity of nlogk
Btw your videos are awesome, just subscribed.
Yes, to do nlogk you need to ensure only k elements are in your minheap at any given time. Maybe I can do a video on that approach
At the moment you might be iterating over every node in every list and putting them all into the heap. This means your heap space will be O(N) and the the time to insert and remove from the heap will be O(logN) (because you have N items in the heap). Instead you can keep only k elements in the heap at one time. This will reduce the space to O(k) and the insert/remove time to O(logk)
Initially put only the heads of each list into the queue. Then when removing from your heap, check if the node you dequeued has a next node. If so enqueue that to the heap
Priority q would work in n log k and more straight forward.
Sir can you explain a little bit more. What is K in O(N*log(K))?
K is the amount of times we must "divide" our array. So in other words, it is how many times we call our recursive function
@@AlgosWithMichael Ok got it. thanks
Priority queue to the rescue.
Yep it is
why didnt you just fill a list by traversing every single node of the list of listnode and then sort it using collection.sort and then create node from that sorted list ?
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy_head = new ListNode(-1);
ListNode result = dummy_head ;
List memory= new ArrayList();
// filling my list
for(int i =0 ; i< lists.length ; i ++ ){
while(lists[i]!= null){
memory.add(lists[i].val);
lists[i]=lists[i].next;
}
}
Collections.sort(memory);
for(int k : memory){
dummy_head.next = new ListNode(k);
dummy_head = dummy_head.next ;
}
return result.next;
}