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 RU-vidrs 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 ?
