@@tanish5662 Can you explain please? There are n linked lists in the 'lists' list and per iteration we merge two items in the list, but we iterate through all items in each element of 'lists' atleast once, so i guess it's O(n log(k))
Hi @@vijethkashyap151, its been 4 weeks and I don't remember my thought process, However I think I got this time complexity as there is a for loop inside while loop. To be precise, by just looking at the code I can say there are 3 nested loops, that might be one of the reason. If u think one of the loop is O(1), just tell me which one. I also remember asking chat gpt 4 about this and it agreed with me.
@terrancejarod5187 First we heapify k elements which can be done in O(k). Then while heap is not empty, we pop from heap with O(lg k), advance the list and push to heap with O(lgk) if list is not none. So apart from the heapify, each node takes O(lgk) time. Time complexity is thus O(k) + O(nlgk) where n is the total number of elements across all lists and k is the number of lists.
I'm not sure if what you described matches the implementation. Am I correct in understanding that the implementation doesn't use a divide and conquer approach but rather merges two lists at a time and then merges the resulting list with the next list in the list of lists? From an arithmetic standpoint, it seems like the sum you're computing follows the pattern k + (k-1) + (k-2) + ... + 1, which simplifies to \( \frac{k(k+1)}{2} \). Consequently, the overall time complexity remains. O(k.n) and not O(nlog k) as with a divide and conquer strategy. Could you confirm if my understanding is correct?
It is a little difficult to see at first but it is divide and conquer. Instead of recursively splitting in half, it merges 2 together and adds the combined list to the *end* . Then takes the next 2 from the *start* of the lists. Say you had four linked lists in lists. lists = [a, b, c, d] Then lists would look like the following after each iteration where the result of merging a and b is ab: [a,b,c,d] [c,d,ab] [ab,cd] [abcd] It's not: [a,b,c,d] [ab,c,d] [abc,d] [abcd] Hope that helps!
@@Ankitb10 The for loop on line 14 takes 2 consecutive (distinct) pairs of indices at a time. So if we start with lists = [a, b, c, d], the first iteration of the for loop merges lists at 0 and 1 (and appends to mergedLists which is now [ab]), and then the second iteration of the for loop merges lists at 2 and 4 (mergedLists is now [ab, cd]). Overall, Before while loop, lists = [a, b, c, d] After first while loop, lists = [ab, cd] After second while loop, lists = [abcd] You can think of it as starting at the leaves of the binary tree and combining 2 *distinct* leaves at each level, so it is indeed log(N).
Thinking about an alternative: Have a priority queue filled with the heads of the lists; pop the smallest, add it to the result list, push the head of the list it originated from, repeat. If I am not mistaken, this should join K lists in O(n).
Inserting an element into a priority queue is O(logn). Inserting n elements would then be O(nlogn). But seeing as you would only ever have k elements in your priority queue, you would get log k. And since you are inserting n nodes, you will get O(nlogk)
@@calvio2835 You don't need any data structures at the end of the day. Might as well do two sum in O(n^2) time but you are definitely not going to pass an interview. How do you think we're going to find the next smallest head? Linear scan? That's inefficient given that you have to do that every single time you move a node. Priority queue is better than running a linear scan every time you pop an element. You don't need a priority queue but since we're optimizing for time, a priority queue is superior. Why run the algorithm in O(nk) time when you could run it in O(nlogk)?
I've come up with the heap solution and I'm glad to know there's also another solution that only uses basic data structures like linked lists to solve it. Pretty amazing!!
I used a sorted deque (ascending) to solve this. When I used the first element, I would pop it, point at the next, then insert into the deque in the correct position based off of the new head. This was fast enough for leetcode's judges, but I don't know how to describe the time complexity of it.
if you implemented the merge 2 lists, we can just start merging from reverse order and remove the merged row from lists: while len(lists) > 1: lists[-2] = merge(lists[-1], lists[-2]) lists.pop() return lists[0] or this option seems better: while len(lists) > 1: for i in range(len(lists)//2): lists[i] = merge(lists[i], lists[-1]) lists.pop() return lists[0]
4:00 n log k complexity is true because each level costs O(n) total and there are log k levels. Wouldn't choose this simple solution without realizing this math first (since there are k-1 steps, doesn't seem like n log k at first glance). So I coded a complicated n log k solution instead xD
The input is a list of linked lists. Say you got 4 lists - the for loop merges 1st and 2nd together into a single linked list and apppends the head of that linked list to the merged_lists (list). Then it merges 3d and 4th together and appends the result (head of the linked list) to the merged_lists again. Now the length of the merged_list is 2 (becase you appended 2 heads). It'll now overwrite the orginal "lists" parameter (4 linked lists) with merged_lists (2 linked lists). Becuse it's greater than 1, it'll run the for loop again merging those 2 linked lists into a single one. Then again it'll overwrite the "lists" parameter (2 linked lists) with merged_lists (1 linked list). At that point the while loop (while len(lists) > 1) exits and returns the head of the linked list.
@@dtcx but why can't we create an empty list - my list = [] and then set my list = merged lists and return mylist[0]? why do we have to overwrite the input? I thought we only care about what we return? why the first doesn't work but the 2nd does? while len(lists) > 1: res = [] merged = [] for i in range(0, len(lists), 2): list1 = lists[i] if (i + 1) < len(lists): list2 = lists[i + 1] else: list2 = None merged.append(self.ml(list1, list2)) res = merged return res[0] vs. while len(lists) > 1: merged = [] for i in range(0, len(lists), 2): list1 = lists[i] if (i + 1) < len(lists): list2 = lists[i + 1] else: list2 = None merged.append(self.ml(list1, list2)) lists = merged return lists[0]
@@OwenWu-f9t functions don't modify things outside their score unless we tell them to, and so lists (outside of the function) will retain its original value e.g. func(x, y): x = 2, y = 1 ## will print x = 2, y = 1 print(x, y) x = 100, y = 200 func(x, y) ## will print x = 100, y 200 print(x, y) and as for why the first one doesn't work-what about when len(lists) == 0?
should be O(n) -- the mergedList array holds 2 lists (as a merged list) whose total number of elements will increase as n increases. K-way merge on a heap is O(k) in space.
Isn't the time complexity O(NKlgK). The first step the depth is lgK and there are k elements. So it is O(KlgK) initially. Now for every subsequent level it is O(KlgK) N/K times. Now to merge all of them together it would be O(NKlgK). using a MinHeap would make it O(NlgK)
mergeKLists can be a recursive function and in this case the code is much cleaner (but I suppose space complexity in this case is O(log k)): def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: n = len(lists) if n == 0: return None elif n == 1: return lists[0]
m = n//2 return self.merge2_lists(self.mergeKLists(lists[:m]), self.mergeKLists(lists[m:]))
Can anyone explain what’s happening on line 17. He mentions he’s going to append it but he instead typed mergelists which is not making sense. Thanks in advance. 7:04
If the original input 'lists' only had a single element we'd skip over the while loop because the condition is 'while len(lists) > 1'. In that case mergedList wouldn't be defined. But returning lists[0] would do the right thing: if there's only a single list it's by definition already merged so we can just return it.
After watching your life story video I just realized this video was uploaded at your life rock bottom... But you still did a great job explaining even at that point!
basically asking for a merge sort algorithm with linked lists structure rather than vectors, which is actually simpler because we don't have to allocate memory.
its a little confusing how you switch back and forth with the definition on "n". Should it be average number of elements in each list or total elements?
I am having doubt, how come the time complexity is O(n log k) ? instead of O ((n*log k) log k) ? I understood the outside (log k) part -> we are going to repeat the merge operations for log k times as the lists size halved each time. (first while loop) But what about the inner for loop and upcoming merge operation for each pair ? In the first while loop: my inner for loop will run k/2 times and each merge operation will cost you n times. so it is (k/2 * n) times In the second while loop: my inner for loop will run k/4 times and merge is n times. so it is (k/4 * n) times right ?
Thanks a lot for the beautiful channel, I am a big fan and love all of your solutions. In this case however I believe an easiest approach is with a min heap (that is also the category where Blind 75 put this problem in): # O(n log k)|O(n+k) where n=total number of nodes, k=number of lists def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: heap = [] for idx, lst in enumerate(lists): if lst: heapq.heappush(heap, (lst.val, idx)) dummy = res = ListNode(0) while heap: _, idx = heapq.heappop(heap) curr = lists[idx] res.next = curr if curr.next: heapq.heappush(heap, (curr.next.val, idx)) lists[idx] = lists[idx].next res = res.next return dummy.next Thanks again and keep up the great work!
funny thing about this (in python) merge sort will not get you the fastest result. you can traverse each listnode and add their vals to a single unsorted list. call python's (reverse) sort method on it. turn this reverse sorted list into a linkedlist, and return that. much faster. but interviewers will prefer to see the merge sort method.
The eastiest to understand solution with O(nlogn) time and O(n) memory complexity is to use Counter, where we store node value as key, and as value number of occurencies in all lists. Then we sort keys in counter and just generate the result. class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: dummy = ListNode(0) tail = dummy counter = Counter()
for single_list in lists: while single_list: counter[single_list.val] += 1 single_list = single_list.next
for key in sorted(counter.keys()): while counter[key] > 0: tail.next = ListNode(key) counter[key] -= 1 tail = tail.next
If you're going to sort the values, there's not really any advantage to storing them in a Counter. You can just put all the values in a Python list and sort that. LeetCode even has that as one of the solutions on their official solutions page: class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: self.nodes = [] head = point = ListNode(0) for l in lists: while l: self.nodes.append(l.val) l = l.next for x in sorted(self.nodes): point.next = ListNode(x) point = point.next return head.next
The solution to this question has some other recommended solutions as well. I get that this is probably the best solution to visualize and explain, but how does it to compare to the others in runtime analysis? Also was anyone else a lil mad when one of the recommended solutions was literally dump everything into an array and sort LOL
Not sure if it's leetcode being weird or not, but the the dump into an array and sort method performed faster for me than this video method. (video method actually didn't complete in time limit for me)
That's what I did when I first saw this problem. It feels kind of like cheating but it works and has a decent time complexity. Probably not what the interviewer is looking for though.
@@lingyuhu4623 Nope it doesn't thats why we use the index. So for e.g lists[idx] represents the next node to add to the heap. Index 0 means that node came from first list and so on
For anyone sugestiong to use heap, heres why you shouldn't: Suppose we have n lists and each list has say k elements. No in order to insert those values to heap, it'll take n*k*log(something). While here its less ig. Please correct me if I am wrong.
His n in O(n*k) and O(n*log(k)) is different from the heap implementation's n in O(n*k*log(k)). In the heap n, n represents the average number of elements in a single linked list, while his n represents the total number of elements in all linked lists. The time complexities are actually the same for both implementations once you account for this difference in the definition of n.
Because by the time the while loop is complete and the length of lists is equal to one, the only list in 'lists' will be the sorted one of all the ListNodes, so you can just return it (which would be the first and only element in lists -> lists[0])
So between this and the heap solution, both have time complexity O(NLogK), but this solution has space complexity O(1) not counting the result as extra space while the heap solution has O(K) space where K is the number of lists. So probably better off learning this solution even though the heap one is simple and efficient, it's not optimal.
@NeetCode, it seems that the complexiy of the first bruteforce is O(k^2*n) and the second is O(k log(k) * n) why? The second make at 1# level: k/2* n, at #2 level we have k/2 lists each with 2n: so we have: k/4 * 2n so we have k/2 * n + k/4 * 2n + k/8 * 4n = n(k/2+ k/2 ...) = n * k * logk
I used a hashmap to kepe track of the seen values(and append after them when seen again). I used two stacks, one for keeping smaller values than current value and other for keeping larger values than current value. I keep poping the values from one and append to another till I find the appropriate place to insert the current value. My solution beats 92% users in runtime with 69ms. But i'm not sure if its he right approach. class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: head = None hashmap = {} stack_left = [float("-infinity")] stack_right = [float("infinity")] for l in lists: curr = l while curr: nxt = curr.next if curr.val in hashmap: temp = hashmap[curr.val].next hashmap[curr.val].next = ListNode(curr.val, temp) curr = hashmap[curr.val].next else: while curr.val < stack_left[-1]: stack_right.append(stack_left.pop()) while curr.val > stack_right[-1]: stack_left.append(stack_right.pop())
if stack_left[-1] > float("-infinity"): temp = hashmap[stack_left[-1]].next hashmap[stack_left[-1]].next = ListNode(curr.val, temp) curr = hashmap[stack_left[-1]].next else: head = ListNode(curr.val, head) curr = head stack_left.append(curr.val) hashmap[curr.val] = curr curr = nxt
Could you just iterate through each linked list and append the values to a stack and then reverse sort the stack, popping off each item while making a new linked list? if not lists: return stack = [] for node in lists: n = node while n: stack.append(n.val) n = n.next stack.sort(reverse=True) if not stack: return retnode = ListNode(stack.pop()) go = retnode while stack: go.next = ListNode(stack.pop()) go = go.next return retnode
Thanks for the video. Very easy way to approach the problem. A minor question. Line # 17 does not work for me. I have to replace with mergeLists.append(self.mergeLists(l1, l2)). What is the difference in your way (without append) and my way ?
Great solution! There is a kind of a bug in your typescript solution but it technically runs anyway regardless of fixing it. For about an hour, I was wondering why it didn't work when I converted it to JavaScript. My while loop in the mergeList function had while not null for l1 and l2 instead of just while l1 and l2. It turns out that line 22 in your solution doesn't ever fire off the else statement, so l2 doesn't get set to None (or null if using another language). It runs because of the while l1 and l2 which accounts for undefined, which is what l2 could be in the case of the first test case with list of length 3. l2 gets declared but doesn't get defined because it never activates the else. Like if len of the lists was 3 and i = 2, it would be compare (2 + 1) > 3. To test it I even removed the else line and it still ran fine. You can fix it by changing it to if (i + 1) > lists.length - 1 to fix it. I would imagine this is also the case with the python solution.
Your comparison opertor should actually be "less than". e.g l2 = lists[i+1] if (i+1) < len(lists) else None. Because you want your index to be less than the length of the list. Otherwise you'll get "list out of range error"
From 2023.9.24 this solution will result in TLE, I am assuming the dummy node initialization and the merging of the two lists is much more inefficient than the priority queue. Any comments?
divide and conquer is used to iterate on the O(nk) approach of merging one by one for each step, `n` nodes (all of them) are compared during the merge process -- O(n) at the end of each step, the number of lists that need to be merged has been halved therefore the number of iterations needed is the number of times you can halve `k` until you get to 1. that is `log k` (base 2). so each step will be done `log k` times -- O(log k) thus the time complexity is O(n log k)
This is wrong, because each step doubles the length of n, so it scales with k. The final merge, for instance, is two lists of about (nk / 2) size. The complexity cannot be lower than one of the steps so it has to be at least nk.
The first merges, are all n steps, but there are k/2 of them. So that is also nk. There are log k steps in this whole process, so the whole complexity is nk log k.
I solved this problem in like 15 minutes but was not efficient, fast but took a ton of memory. other problems that are medium and easy took me hours vs this hard problem. (im not even smart lol)
What's the point of line 18, the one that sets "lists" equal to "mergedLists"? : while len(lists) > 1: mergedLists = [] for i in range(0, len(lists), 2): l1 = lists[i] l2 = lists[i + 1] if (i + 1) < len(lists) else None mergedLists.append(self.mergeList(l1, l2)) lists = mergedLists return lists[0]
You can imagine lists is [[1],[2],[3],[4],[5],[6]],after first mergeList, the mergedLists becomes[[1,2],[3,4],[5,6]],then let this mergedLists become Lists again, so the “while len(Lists)>1:” is true again and you start a new loop, and then you do it again becomes[[1,2,3,4],[5,6]], then finally the List becomes[[1,2,3,4,5,6]],return Lists[0]
I was so confused by this because I didn't realize the number 2 in "for I in range" line meant how much to increment by and not that the range of i was only from 0 to 2 😭 I was like why is the for loop only executing once
We have k lists and we group them into k/2 pairs, then merge each pair. Now we have k/2 lists and we merged that into k/4 pairs. So we are dividing the number of lists in half each time. E.g. Say we have four lists. Merge list 1 and list 2 together, and merge list 3 and list 4 together. That gives us two merged lists. Now merge those two into a single result.
Why is the approach showed in the video better than the following approach? dummy = ListNode() min_node = all_lists[0] while len(all_lists): i = 0 while i < len(all_lists) if node is None: all_lists.pop(i) elif node.val < min_node.val: min_node = node i += 1 dummy.next = min_node I don't see why it would be slower.
It still works, you just have to make sure "l2 = lists[i+1] if (i+1) < len(lists) else None" is written out correctly, if you do it another way then it won't work. Otherwise you can use the heap method.
the most straighforward intuitive approach is. just iterate through all the linked list and get their values append those values to a list. then sort. then just convert the combined sorted list to a linked list. there were no restrictions so its the simplest approach. that approach beats 80% of python submissions
your solution would be O(NK*log(NK)) time and O(NK) space where K is the # of lists and N is average length of lists. The optimal solution is O(NK*log(K)) time and O(K) space. It's important to use big O when analyzing optimal, interviewers do not care about Leetcode submission times
I'm curious about the space complexity in this solution, since we are creating a new list called mergedLists in the while loop, so I think we will create logK lists, so space complexity should be logK, right?
With Neetcode's implementation, mergedList is the only source of non-constant space complexity. As the length of lists (our input) increases, mergedList at its worst case stores k // 2 (O(k)) partially merged lists on the first pass of the merge step. Therefore, space complexity is O(k). O(log(k)) is how many passes the merge step will take to make lists length 1. On each pass, the helper merge two lists method takes O(n) where n is the combined length of the two lists. Therefore, time complexity is O(n*logk).
as long as your have more than one sublist in your lists input, you have to keep merging them together, so while len(lists) is not bigger than 1 meaning we have 1 or less lists, then we have our result and want to return the final list
this implementation is simpler and it keeps the same runtime complexity (tho it runs slower in leetcode) class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: res = None for l in lists: res = merge(res, l) return res
I think time complexity of 1st solution should be O(n2k) and for optimized solution O(nlognk). where n is size of array , k size of list. if I am wrong plz somebody help. Thanks in advance.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Rem best girl
I have a doubt on the time complexity in this question, I got log(Nklogk) as there is for loop inside while loop, Am i right? Please reply
@@tanish5662 Can you explain please? There are n linked lists in the 'lists' list and per iteration we merge two items in the list, but we iterate through all items in each element of 'lists' atleast once, so i guess it's O(n log(k))
Hi @@vijethkashyap151, its been 4 weeks and I don't remember my thought process, However I think I got this time complexity as there is a for loop inside while loop. To be precise, by just looking at the code I can say there are 3 nested loops, that might be one of the reason. If u think one of the loop is O(1), just tell me which one. I also remember asking chat gpt 4 about this and it agreed with me.
I love the way you get right into the crux of the problem rather explaining unwanted details. Cool video and keep them coming, thanks.
I code in Java, but with your explanations, I do not even need to look at your code. Keep up the good work!! You make everything super simple!!
You are the best at simplifying problems ... Glad I found you.
Bro is a genius , breaks down hard problems into such easy solutions.
Nice solution! But you can also use heap which is much easier and more simple.
heap runs in O(knlogn) which is a lot slower than O(nlogn) which is the time complexity of the solution in the video
@@terrancejarod5187 its wrong to say O(knlogn).It would be O(nlogk)
I implemented both in Java using PriorityQueue (Heap) and the one from this video, runtime is quite similar. I think both are O(n log k)
@terrancejarod5187 First we heapify k elements which can be done in O(k). Then while heap is not empty, we pop from heap with O(lg k), advance the list and push to heap with O(lgk) if list is not none. So apart from the heapify, each node takes O(lgk) time.
Time complexity is thus O(k) + O(nlgk) where n is the total number of elements across all lists and k is the number of lists.
I'm not sure if what you described matches the implementation. Am I correct in understanding that the implementation doesn't use a divide and conquer approach but rather merges two lists at a time and then merges the resulting list with the next list in the list of lists? From an arithmetic standpoint, it seems like the sum you're computing follows the pattern k + (k-1) + (k-2) + ... + 1, which simplifies to \( \frac{k(k+1)}{2} \). Consequently, the overall time complexity remains. O(k.n) and not O(nlog k) as with a divide and conquer strategy. Could you confirm if my understanding is correct?
I have the same doubt. I also feel it is O(kn)
It is a little difficult to see at first but it is divide and conquer. Instead of recursively splitting in half, it merges 2 together and adds the combined list to the *end* . Then takes the next 2 from the *start* of the lists.
Say you had four linked lists in lists. lists = [a, b, c, d]
Then lists would look like the following after each iteration where the result of merging a and b is ab:
[a,b,c,d]
[c,d,ab]
[ab,cd]
[abcd]
It's not:
[a,b,c,d]
[ab,c,d]
[abc,d]
[abcd]
Hope that helps!
@@Ankitb10 The for loop on line 14 takes 2 consecutive (distinct) pairs of indices at a time. So if we start with lists = [a, b, c, d], the first iteration of the for loop merges lists at 0 and 1 (and appends to mergedLists which is now [ab]), and then the second iteration of the for loop merges lists at 2 and 4 (mergedLists is now [ab, cd]).
Overall,
Before while loop, lists = [a, b, c, d]
After first while loop, lists = [ab, cd]
After second while loop, lists = [abcd]
You can think of it as starting at the leaves of the binary tree and combining 2 *distinct* leaves at each level, so it is indeed log(N).
Thinking about an alternative:
Have a priority queue filled with the heads of the lists;
pop the smallest,
add it to the result list,
push the head of the list it originated from,
repeat.
If I am not mistaken, this should join K lists in O(n).
Inserting an element into a priority queue is O(logn). Inserting n elements would then be O(nlogn).
But seeing as you would only ever have k elements in your priority queue, you would get log k. And since you are inserting n nodes, you will get O(nlogk)
It is O(nlogk) runtime and O(k) space which is almost as good as mergesort but not O(1) space
@@Dun1007 Merge sort should be O(n) space.
Why do you need a priority queue to compare and find smallest head? It just becomes finding smallest node in list of nodes
@@calvio2835 You don't need any data structures at the end of the day. Might as well do two sum in O(n^2) time but you are definitely not going to pass an interview. How do you think we're going to find the next smallest head? Linear scan? That's inefficient given that you have to do that every single time you move a node. Priority queue is better than running a linear scan every time you pop an element.
You don't need a priority queue but since we're optimizing for time, a priority queue is superior. Why run the algorithm in O(nk) time when you could run it in O(nlogk)?
First leetcode Hard I solved myself, thanks to your awesome explanations! Of course, seems like this problem really is a medium lol.
I've come up with the heap solution and I'm glad to know there's also another solution that only uses basic data structures like linked lists to solve it. Pretty amazing!!
Thank you for the explanation! I believe the complexity in the initial (brute force) algorithm is nk^2 and in this algorithm is nklog(k)
I used a sorted deque (ascending) to solve this. When I used the first element, I would pop it, point at the next, then insert into the deque in the correct position based off of the new head.
This was fast enough for leetcode's judges, but I don't know how to describe the time complexity of it.
inserting anything in the middle of a sequence is O(n) worst case. your solution would be O(n^2).
btw u can simply it by using a queue. Convert the lists into a queue, and then u can simply popleft and append at the end
q=deque([l for l in lists])
while len(q)!=1:
l1=q.popleft()
l2=q.popleft()
mList=merge(l1,l2)
q.append(mList)
return q[0]
you explain Leetcode HARD in 5 minutes (P.S i watch in 2x). you are awesome bro. i am your fan
Thank you Sir. Very well explained. My favorite youtube channel for python/leetcode studies.
if you implemented the merge 2 lists, we can just start merging from reverse order and remove the merged row from lists:
while len(lists) > 1:
lists[-2] = merge(lists[-1], lists[-2])
lists.pop()
return lists[0]
or this option seems better:
while len(lists) > 1:
for i in range(len(lists)//2):
lists[i] = merge(lists[i], lists[-1])
lists.pop()
return lists[0]
4:00 n log k complexity is true because each level costs O(n) total and there are log k levels. Wouldn't choose this simple solution without realizing this math first (since there are k-1 steps, doesn't seem like n log k at first glance). So I coded a complicated n log k solution instead xD
I don't quite understand line 18. Wouldn't it replace the original 'lists' parameter? If so, where do the rest of the lists to be merged go?
The input is a list of linked lists. Say you got 4 lists - the for loop merges 1st and 2nd together into a single linked list and apppends the head of that linked list to the merged_lists (list). Then it merges 3d and 4th together and appends the result (head of the linked list) to the merged_lists again. Now the length of the merged_list is 2 (becase you appended 2 heads). It'll now overwrite the orginal "lists" parameter (4 linked lists) with merged_lists (2 linked lists). Becuse it's greater than 1, it'll run the for loop again merging those 2 linked lists into a single one. Then again it'll overwrite the "lists" parameter (2 linked lists) with merged_lists (1 linked list). At that point the while loop (while len(lists) > 1) exits and returns the head of the linked list.
@@dtcx but why can't we create an empty list - my list = [] and then set my list = merged lists and return mylist[0]? why do we have to overwrite the input? I thought we only care about what we return? why the first doesn't work but the 2nd does?
while len(lists) > 1:
res = []
merged = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if (i + 1) < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged.append(self.ml(list1, list2))
res = merged
return res[0]
vs.
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
list1 = lists[i]
if (i + 1) < len(lists):
list2 = lists[i + 1]
else:
list2 = None
merged.append(self.ml(list1, list2))
lists = merged
return lists[0]
@@OwenWu-f9t functions don't modify things outside their score unless we tell them to, and so lists (outside of the function) will retain its original value
e.g.
func(x, y):
x = 2, y = 1
## will print x = 2, y = 1
print(x, y)
x = 100, y = 200
func(x, y)
## will print x = 100, y 200
print(x, y)
and as for why the first one doesn't work-what about when len(lists) == 0?
great explanation! Very clear and concise!
thank you very much, I personally think the previous LRU cache problem should be in hard category instead of this one .
What's the space complexity of this?
O(1)
should be O(n) -- the mergedList array holds 2 lists (as a merged list) whose total number of elements will increase as n increases. K-way merge on a heap is O(k) in space.
Not sure about Python but it is O(1) space for C++ where you don’t have to use additional space but you just need to move the pointers
Clearly is O(n)
Pointers are also taking space bro@@charleskorey6515
You are the legend. Thank you for your job
GENIUS PLZ DON'T STOP
You're awesome man, can't thank you enough!
Isn't the time complexity O(NKlgK). The first step the depth is lgK and there are k elements. So it is O(KlgK) initially. Now for every subsequent level it is O(KlgK) N/K times. Now to merge all of them together it would be O(NKlgK).
using a MinHeap would make it O(NlgK)
Hey! which keyboard do you use?
mergeKLists can be a recursive function and in this case the code is much cleaner (but I suppose space complexity in this case is O(log k)):
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
if n == 0:
return None
elif n == 1:
return lists[0]
m = n//2
return self.merge2_lists(self.mergeKLists(lists[:m]), self.mergeKLists(lists[m:]))
Really good explanation!
Can anyone explain what’s happening on line 17. He mentions he’s going to append it but he instead typed mergelists which is not making sense. Thanks in advance. 7:04
Why do you have to return lists[0]? Could we just return mergedList?
If the original input 'lists' only had a single element we'd skip over the while loop because the condition is 'while len(lists) > 1'. In that case mergedList wouldn't be defined. But returning lists[0] would do the right thing: if there's only a single list it's by definition already merged so we can just return it.
pretty sophisticated and enrapturing solution , and I think alternatively we could pick out minheap to sort this problem
For loops for divide and conquer instead of recursion. Nice
Thanks for your explanation. Can you please make a video that explains the Leetcode 632: Smallest range covering elements from K lists?
Great video! Does the mergedLists variable take up O(K) memory complexity?
After watching your life story video I just realized this video was uploaded at your life rock bottom... But you still did a great job explaining even at that point!
This is clever! Is it considered a divide and conquer solution?
Thanks sir, These videos are very help full.
How the case of len(lists)==1 will be handled?
Hii @NeetCode can u plz explain, what is the difference between 'len(lists) == 0' and 'not list'.
I'm curious about that too.
I think its 1. A empty list and 2. NULL value
It's the same. Either of them will check for empty list.
@@mindsetnuggets thanks
the first if statement can just be `if not lists`...that'll check if the list is empty.
basically asking for a merge sort algorithm with linked lists structure rather than vectors, which is actually simpler because we don't have to allocate memory.
its a little confusing how you switch back and forth with the definition on "n". Should it be average number of elements in each list or total elements?
Thank you Neet!
I am having doubt, how come the time complexity is O(n log k) ? instead of O ((n*log k) log k) ?
I understood the outside (log k) part -> we are going to repeat the merge operations for log k times as the lists size halved each time. (first while loop)
But what about the inner for loop and upcoming merge operation for each pair ?
In the first while loop: my inner for loop will run k/2 times and each merge operation will cost you n times.
so it is (k/2 * n) times
In the second while loop: my inner for loop will run k/4 times and merge is n times.
so it is (k/4 * n) times
right ?
same thoughts here, @NeetCode could you please explain?
Thanks a lot for the beautiful channel, I am a big fan and love all of your solutions. In this case however I believe an easiest approach is with a min heap (that is also the category where Blind 75 put this problem in):
# O(n log k)|O(n+k) where n=total number of nodes, k=number of lists
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for idx, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, idx))
dummy = res = ListNode(0)
while heap:
_, idx = heapq.heappop(heap)
curr = lists[idx]
res.next = curr
if curr.next:
heapq.heappush(heap, (curr.next.val, idx))
lists[idx] = lists[idx].next
res = res.next
return dummy.next
Thanks again and keep up the great work!
space complexity is O(N) for priority queue, with merge sort you're splicing the lists together
@@konark709 what is the space complexity for the above algorithm?
Can we use recursion (divide and conquer) instead of the for loop to parse through the list?
I.m also having the same thought process, like using merge sort
I think it takes more memory. Correct me If I'm wrong.
That is pretty neat solution & explanation, beats 1.7x my minHeap solution
Thank you soo much for this!!
funny thing about this (in python)
merge sort will not get you the fastest result.
you can traverse each listnode and add their vals to a single unsorted list. call python's (reverse) sort method on it. turn this reverse sorted list into a linkedlist, and return that. much faster.
but interviewers will prefer to see the merge sort method.
The eastiest to understand solution with O(nlogn) time and O(n) memory complexity is to use Counter, where we store node value as key, and as value number of occurencies in all lists. Then we sort keys in counter and just generate the result.
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
counter = Counter()
for single_list in lists:
while single_list:
counter[single_list.val] += 1
single_list = single_list.next
for key in sorted(counter.keys()):
while counter[key] > 0:
tail.next = ListNode(key)
counter[key] -= 1
tail = tail.next
return dummy.next
If you're going to sort the values, there's not really any advantage to storing them in a Counter. You can just put all the values in a Python list and sort that. LeetCode even has that as one of the solutions on their official solutions page:
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
self.nodes = []
head = point = ListNode(0)
for l in lists:
while l:
self.nodes.append(l.val)
l = l.next
for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next
return head.next
get it thanks a lot!
Do #43 and #73 on the list are repeated? Both of them are 'Merge K Sorted Lists'~~
Good chatch. I guess two ways to solve the problem: Divide-and-Conquer and Heap
The solution to this question has some other recommended solutions as well. I get that this is probably the best solution to visualize and explain, but how does it to compare to the others in runtime analysis?
Also was anyone else a lil mad when one of the recommended solutions was literally dump everything into an array and sort LOL
Not sure if it's leetcode being weird or not, but the the dump into an array and sort method performed faster for me than this video method. (video method actually didn't complete in time limit for me)
That's what I did when I first saw this problem. It feels kind of like cheating but it works and has a decent time complexity. Probably not what the interviewer is looking for though.
@@OM-el6oy The time complexity is too slow. He's hiding it for the views.
@@OM-el6oy He's using a brute force approach, and not using divide and conquer.
Using heaps
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for idx,element in enumerate(lists):
print(element)
if element:
heappush(heap,(element.val,idx))
dummy = curr = ListNode(0)
while heap:
val,idx = heappop(heap)
curr.next = ListNode(val)
curr = curr.next
if lists[idx].next:
lists[idx] = lists[idx].next
heappush(heap,(lists[idx].val,idx))
return dummy.next
Hello, does priority queue support compare between instances of ListNode?
@@lingyuhu4623 Nope it doesn't thats why we use the index. So for e.g lists[idx] represents the next node to add to the heap. Index 0 means that node came from first list and so on
i think using heaps (k-way merge) would have been cleaner
For anyone sugestiong to use heap, heres why you shouldn't:
Suppose we have n lists and each list has say k elements.
No in order to insert those values to heap, it'll take n*k*log(something). While here its less ig. Please correct me if I am wrong.
His n in O(n*k) and O(n*log(k)) is different from the heap implementation's n in O(n*k*log(k)). In the heap n, n represents the average number of elements in a single linked list, while his n represents the total number of elements in all linked lists. The time complexities are actually the same for both implementations once you account for this difference in the definition of n.
why return lists[0]?
Because by the time the while loop is complete and the length of lists is equal to one, the only list in 'lists' will be the sorted one of all the ListNodes, so you can just return it (which would be the first and only element in lists -> lists[0])
@@KolydoscopeMusic thx！！
Center blew the snap, you coding style as good as the sound from your keyboard
So between this and the heap solution, both have time complexity O(NLogK), but this solution has space complexity O(1) not counting the result as extra space while the heap solution has O(K) space where K is the number of lists. So probably better off learning this solution even though the heap one is simple and efficient, it's not optimal.
is this a duplicated in blind75 list?
What's the complexity of this solution?
@NeetCode, it seems that the complexiy of the first bruteforce is O(k^2*n) and the second is O(k log(k) * n)
why?
The second make at 1# level: k/2* n,
at #2 level we have k/2 lists each with 2n: so we have: k/4 * 2n
so we have k/2 * n + k/4 * 2n + k/8 * 4n = n(k/2+ k/2 ...) = n * k * logk
I used a hashmap to kepe track of the seen values(and append after them when seen again).
I used two stacks, one for keeping smaller values than current value and other for keeping larger values than current value. I keep poping the values from one and append to another till I find the appropriate place to insert the current value.
My solution beats 92% users in runtime with 69ms. But i'm not sure if its he right approach.
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
head = None
hashmap = {}
stack_left = [float("-infinity")]
stack_right = [float("infinity")]
for l in lists:
curr = l
while curr:
nxt = curr.next
if curr.val in hashmap:
temp = hashmap[curr.val].next
hashmap[curr.val].next = ListNode(curr.val, temp)
curr = hashmap[curr.val].next
else:
while curr.val < stack_left[-1]:
stack_right.append(stack_left.pop())
while curr.val > stack_right[-1]:
stack_left.append(stack_right.pop())
if stack_left[-1] > float("-infinity"):
temp = hashmap[stack_left[-1]].next
hashmap[stack_left[-1]].next = ListNode(curr.val, temp)
curr = hashmap[stack_left[-1]].next
else:
head = ListNode(curr.val, head)
curr = head
stack_left.append(curr.val)
hashmap[curr.val] = curr
curr = nxt
return head
Could you just iterate through each linked list and append the values to a stack and then reverse sort the stack, popping off each item while making a new linked list?
if not lists:
return
stack = []
for node in lists:
n = node
while n:
stack.append(n.val)
n = n.next
stack.sort(reverse=True)
if not stack:
return
retnode = ListNode(stack.pop())
go = retnode
while stack:
go.next = ListNode(stack.pop())
go = go.next
return retnode
Thanks for the video. Very easy way to approach the problem. A minor question. Line # 17 does not work for me. I have to replace with mergeLists.append(self.mergeLists(l1, l2)). What is the difference in your way (without append) and my way ?
He fixes it to your way later on in the video. It was a mistake.
Why not use a maxheap?
What is n here? total number of the nodes?
Great solution! There is a kind of a bug in your typescript solution but it technically runs anyway regardless of fixing it. For about an hour, I was wondering why it didn't work when I converted it to JavaScript. My while loop in the mergeList function had while not null for l1 and l2 instead of just while l1 and l2. It turns out that line 22 in your solution doesn't ever fire off the else statement, so l2 doesn't get set to None (or null if using another language). It runs because of the while l1 and l2 which accounts for undefined, which is what l2 could be in the case of the first test case with list of length 3. l2 gets declared but doesn't get defined because it never activates the else. Like if len of the lists was 3 and i = 2, it would be compare (2 + 1) > 3. To test it I even removed the else line and it still ran fine. You can fix it by changing it to if (i + 1) > lists.length - 1 to fix it. I would imagine this is also the case with the python solution.
Your comparison opertor should actually be "less than". e.g l2 = lists[i+1] if (i+1) < len(lists) else None. Because you want your index to be less than the length of the list. Otherwise you'll get "list out of range error"
it didn't come up to me that this is exactly the merge sort, even though I noticed the pattern in the two merge problem
From 2023.9.24 this solution will result in TLE, I am assuming the dummy node initialization and the merging of the two lists is much more inefficient than the priority queue. Any comments?
No it doesn't fail. The code is passing all the test cases in LC 2023.12.29
Yeah it results TLE 2024.06.03
everyone suggesting a minheap solution is forgetting the fact that this solutions runs in O(1) memory. heap needs extra space.
Can you also focus on the space complexity while solving a question please
divide and conquer is used to iterate on the O(nk) approach of merging one by one
for each step, `n` nodes (all of them) are compared during the merge process -- O(n)
at the end of each step, the number of lists that need to be merged has been halved
therefore the number of iterations needed is the number of times you can halve `k` until you get to 1. that is `log k` (base 2). so each step will be done `log k` times -- O(log k)
thus the time complexity is O(n log k)
what's the space complexity?
This is wrong, because each step doubles the length of n, so it scales with k.
The final merge, for instance, is two lists of about (nk / 2) size. The complexity cannot be lower than one of the steps so it has to be at least nk.
The first merges, are all n steps, but there are k/2 of them.
So that is also nk.
There are log k steps in this whole process, so the whole complexity is nk log k.
Whats the space complexity?
O(k), `k` is number of linked lists
auxiliary space is used in the `mergedLists` variable
I solved this problem in like 15 minutes but was not efficient, fast but took a ton of memory. other problems that are medium and easy took me hours vs this hard problem. (im not even smart lol)
for me , an easy way to solve this problem was with a priority queue
What's the point of line 18, the one that sets "lists" equal to "mergedLists"? :
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
mergedLists.append(self.mergeList(l1, l2))
lists = mergedLists
return lists[0]
You can imagine lists is [[1],[2],[3],[4],[5],[6]],after first mergeList, the mergedLists becomes[[1,2],[3,4],[5,6]],then let this mergedLists become Lists again, so the “while len(Lists)>1:” is true again and you start a new loop, and then you do it again becomes[[1,2,3,4],[5,6]], then finally the List becomes[[1,2,3,4,5,6]],return Lists[0]
I was so confused by this because I didn't realize the number 2 in "for I in range" line meant how much to increment by and not that the range of i was only from 0 to 2 😭 I was like why is the for loop only executing once
@@evynsrefuge for I in range(starting, uptonotinaluding, stepsize):
there's a linear time solution using hash map
def mergeKLists(lists):
result = sum(lists, [])
return sorted(result)
did u purposely pick those numbers to add up to 23?
i cant understand why it is nlogk not n*k
See, in each iteration we are traversing all the node and the total number of iterations is logk, that's why
How come this one is considered as a divide and conquer ? can't wrap my head around
We have k lists and we group them into k/2 pairs, then merge each pair. Now we have k/2 lists and we merged that into k/4 pairs. So we are dividing the number of lists in half each time.
E.g. Say we have four lists. Merge list 1 and list 2 together, and merge list 3 and list 4 together. That gives us two merged lists. Now merge those two into a single result.
Why is the approach showed in the video better than the following approach?
dummy = ListNode()
min_node = all_lists[0]
while len(all_lists):
i = 0
while i < len(all_lists)
if node is None:
all_lists.pop(i)
elif node.val < min_node.val:
min_node = node
i += 1
dummy.next = min_node
I don't see why it would be slower.
Does anyone encounter a problem with this problem? I used the same code but it won't work in lc since the time exceeds
It still works, you just have to make sure "l2 = lists[i+1] if (i+1) < len(lists) else None" is written out correctly, if you do it another way then it won't work. Otherwise you can use the heap method.
Recursive solution using mergeSort:
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists:
return None
return self.merge_sort(lists)[0]
def merge_sort(self, nodes):
if len(nodes) == 1:
return nodes
# print(nodes)
middle = len(nodes) // 2
nodes_left = self.merge_sort(nodes[0: middle])
nodes_right = self.merge_sort(nodes[middle: len(nodes)])
return self.merge(nodes_left[0], nodes_right[0])
def merge(self, nodes_left, nodes_right):
head = ListNode(-1)
tail = head
while nodes_left and nodes_right:
if nodes_left.val
the most straighforward intuitive approach is.
just iterate through all the linked list and get their values append those values to a list.
then sort.
then just convert the combined sorted list to a linked list.
there were no restrictions so its the simplest approach.
that approach beats 80% of python submissions
your solution would be O(NK*log(NK)) time and O(NK) space where K is the # of lists and N is average length of lists. The optimal solution is O(NK*log(K)) time and O(K) space.
It's important to use big O when analyzing optimal, interviewers do not care about Leetcode submission times
I'm curious about the space complexity in this solution, since we are creating a new list called mergedLists in the while loop, so I think we will create logK lists, so space complexity should be logK, right?
With Neetcode's implementation, mergedList is the only source of non-constant space complexity. As the length of lists (our input) increases, mergedList at its worst case stores k // 2 (O(k)) partially merged lists on the first pass of the merge step. Therefore, space complexity is O(k).
O(log(k)) is how many passes the merge step will take to make lists length 1. On each pass, the helper merge two lists method takes O(n) where n is the combined length of the two lists. Therefore, time complexity is O(n*logk).
Using heapq
class Solution:
def mergeKLists(self, nList: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(nList) == 0: return None
heap = []
for i in range(len(nList)):
if not nList[i]: continue
heapq.heappush(heap, (nList[i].val, i, nList[i]))
if len(heap) == 0: return None
dummy = ListNode(0)
d_node = dummy
while heap:
val, j , node = heapq.heappop(heap)
d_node.next = node
d_node = d_node.next
if node.next:
heapq.heappush(heap, (node.next.val, j, node.next))
return dummy.next
I'm quite surprised you didn't use a heap :/
👍
Can any one explain why While len(lists)> 1 is used????
as long as your have more than one sublist in your lists input, you have to keep merging them together, so while len(lists) is not bigger than 1 meaning we have 1 or less lists, then we have our result and want to return the final list
I really question the runtime analysis here.
awesome
this implementation is simpler and it keeps the same runtime complexity (tho it runs slower in leetcode)
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
res = None
for l in lists:
res = merge(res, l)
return res
no it has a different runtime. it's literally the code equivalent of the example he went through at the start, and its O(nk).
@@hoixthegreat8359 you are correct, I found out later and forgot I did the comment
Similar code using 'heapq' and iterators
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def l_iter(self):
_iter = self
while _iter:
yield _iter.val
_iter = _iter.next
ListNode.__iter__ = l_iter
filtered_lists = filter(lambda x: x is not None, lists)
list_head = list_tail = None
counter = count(0)
stack = []
for l in filtered_lists:
itr = iter(l)
heapq.heappush(stack, (next(itr), next(counter), itr))
while stack:
try:
val, _, itr = heapq.heappop(stack)
if not list_head:
list_head = list_tail = ListNode(val)
else:
list_tail.next = ListNode(val)
list_tail = list_tail.next
heapq.heappush(stack, (next(itr), next(counter), itr))
except:
pass
return list_head
Can I have the same question solution in Java?
best
learn leetcode in here to beat 100 liked question
Anyone getting type error for this solution
im getting index out of range error for l1 even though its only while len lists > 1 idk
I think time complexity of 1st solution should be O(n2k) and for optimized solution O(nlognk).
where n is size of array , k size of list.
if I am wrong plz somebody help.
Thanks in advance.