Merge K Sorted Lists - Leetcode 23 - Python

Показать описание

0:00 - Conceptual Solution
4:40 - Coding solution

#leetcode #mergesort #linkedlist

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

NeetCode

Рекомендации по теме

Комментарии

I love the way you get right into the crux of the problem rather explaining unwanted details. Cool video and keep them coming, thanks.

pawandeepchor

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!!

lugiadark

Bro is a genius, breaks down hard problems into such easy solutions.

usmanmalik-xkvi

Nice solution! But you can also use heap which is much easier and more simple.

lilianjiang

You are the best at simplifying problems ... Glad I found you.

sistaseetaram

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).

pekarna

First leetcode Hard I solved myself, thanks to your awesome explanations! Of course, seems like this problem really is a medium lol.

Urvashiful

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

cc-tojn

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!!

n.h.son

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)

Fatmatlili

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.

thisisnotok

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]

idgafa

thank you very much, I personally think the previous LRU cache problem should be in hard category instead of this one .

MOHDABDULRAHMAN-oe

you explain Leetcode HARD in 5 minutes (P.S i watch in 2x). you are awesome bro. i am your fan

devakinandan

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:]))

PerseRos

pretty sophisticated and enrapturing solution, and I think alternatively we could pick out minheap to sort this problem

NEO-wlox

Thank you Sir. Very well explained. My favorite youtube channel for python/leetcode studies.

shashikantdivekar

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

zl

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)

RaoVenu

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)

RM-xrlq

Merge K Sorted Lists - Leetcode 23 - Python

Merge K Sorted Lists - Leetcode 23 - Python

L25. Merge K Sorted Lists | Multiple Approaches

Merge K Sorted Linked Lists - Leetcode 23 - Heaps (Python)

Merge K Sorted Arrays - Min Heap Algorithm ('Merge K Sorted Lists' on LeetCode)

Merge K Sorted Lists

Merge K Sorted Linked Lists - Leetcode 23

Merge k Sorted Lists | Live Coding with Explanation | Leetcode - 23

Merge k Sorted Lists | Решение на Python | LeetCode 23

Merge K sorted lists | Leetcode #23

Merge k Sorted Lists - (Leetcode - 23) - (Google, Amazon, Microsoft..) : Explanation ➕ Live Coding

MERGE K SORTED LISTS | LEETCODE 23 | PYTHON OPTIMAL SOLUTIO

HARD Faang Interview Question | Merge K Sorted Linked Lists - Leetcode 23

Leetcode - Merge k Sorted Lists (Python)

Leetcode - Merge k Sorted Lists (Python) (Revisited)

Merge K Sorted Lists - Divide and Conquer Approach

Merge k Sorted Lists | LeetCode 23 | C++

Get Huge with Merge K Sorted Linked Lists - Leetcode 23

Merge k Sorted Lists Python Solution - LeetCode #23

Merge K Sorted Lists (LeetCode) | Interview Question Explained

Merge K sorted lists | Leetcode 23 | Leetcode Hard 🔥🔥🔥| 2 Approaches | K log K | Live coding session...

Merge k Sorted Lists | Merge k Sorted Lists LeetCode Java | LeetCode - Hard- 23

Merge k sorted lists #Interviewbit C++ Code and Intuition and Examples

Mastering Leetcode Merge K-Sorted Lists at Lightning Speed

Leetcode 23 - Merge K Sorted Lists (JAVA Solution Explained!)