Merge k Sorted Lists - (Leetcode - 23) - (Google, Amazon, Microsoft..) : Explanation ➕ Live Coding
Vložit
- čas přidán 10. 03. 2023
- This is the 8th Video on our Linked List Playlist.
In this video we will try to solve another interesting and very popular Linked List problem "Merge k Sorted Lists" (Leetcode-23).
Although it's marked hard, this will be so much easier to understand.
Problem Name : Merge k Sorted Lists
Company Tags : VMWare, Amazon, Uber, Google, Twitter, LinkedIn, Airbnb, Facebook, Microsoft, IXL
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/merge-k...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
![The moment we stopped understanding AI [AlexNet]](http://i.ytimg.com/vi/UZDiGooFs54/mqdefault.jpg)
Unbelievable! How are you so so good bhai? Java Implementation:
class Solution {
private ListNode mergeTwoSortedList(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val l2.val) {
l2.next = mergeTwoSortedList(l1,l2.next);
return l2;
}
return null;
}
private ListNode paritionAndMerge(int s, int e, ListNode[] lists) {
if(s > e) {
return null;
}
if(s == e) {
return lists[s];
}
int mid = s +(e-s)/2;
ListNode L1 = paritionAndMerge(s,mid,lists);
ListNode L2 = paritionAndMerge(mid+1,e,lists);
return mergeTwoSortedList(L1,L2);
}
public ListNode mergeKLists(ListNode[] lists) {
int k = lists.length;
if(k == 0) {
return null;
}
return paritionAndMerge(0,k-1,lists);
}
}
You are just awesome !!.. Cant believe i wrote the code myself after listening to this video !!
great video
I think you are the best who can make things easier like a cake walk
This question felt hard for me when I initially attempted it. But, now it feels quite easy.
Thank you so much bhai for making this question very easy to understand 🙌❤.
Please bhaiya, it's my humble request to you please don't stop teaching dsa and cp and posting videos on solving question.. It help's a lot. After 5-6 months companies are going to visit our college so you and your channel is going to help me and my friends alot....Lots of love from jabalpur (MP)
Same bro
placement hoa kya bhai ??
@@nawazthezaifre8870 placement hua?
too good man. becoming your fan day by day. One stop for revision
awesome bhaiya😍
Bhai kya smjhate ho❤️❤️
Amazing explanation🌹
the best explanation
You are genius ,
Best explanation
can't we use a for loop in which we merge first two then we will merge the answer of that to next list and like that isn't that a good way?
🔥🔥
What is the need of partition and merge, we can simply use a for loop from i =2 to n-1 and merge the result of lists[0] & lists[1] with lists[i] . At each iteration mergedList = merge(lists[i],mergedList) ...
@codestorywithMIK ek baar just Merge K sorted array wala ...explain kardo ya github pe upload kardo please
very good explanation
pls make video on today leetcode contest questions
I will soon start those as well . Just trying to make plans as per my time management. Soon
very nice bhai;
Thank You soo much sir !!
You really made it easy
I am so glad it helped ❤️❤️❤️
Masterful !!
Thank you so much 🙏❤️😇
Bhaiya weekly contests ke questions par bhi video bana dijiye please.
I will soon start those as well . Just trying to make plans as per my time management. Soon
Good one. Just want to point out that currently the time complexity is O(NlogK) and space complexity is O(logK) because of recursion stack, it can be solved iteratively with the same time complexity but with O(1) space complexity.
Indeed
yup.. we could use the iterative approach to merge the two lists
Beautiful solution brother, I solved it using PriorityQueue now will solve using your approach
public class Pair implements Comparable {
ListNode node;
public Pair(ListNode node){
this.node = node;
}
@Override
public int compareTo(Pair o){
return this.node.val - o.node.val;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0) return null;
ListNode res = new ListNode(-1);
ListNode t = res;
PriorityQueue pq = new PriorityQueue();
for(int i=0;i 0){
Pair rem = pq.remove();
t.next = rem.node;
t = t.next;
if(rem.node.next != null){
pq.add(new Pair(rem.node.next));
}
}
return res.next;
}
you explained so nicely keep making such videos
Thank you so much 😇🙏
@@codestorywithMIK please create video on quick sort on linked list , i want your approach to solve this thanks
If I submit Python code then
There is TLE error if we submit using an iterative approach
There is a maximum recursive depth error if I follow the recursive approach.
what will be the recurrence relation for the given algorithm? If it is T(k) = 2*T(k/2)+n then it will result in n*k or if it is not the correct recurrence relation then what will be the correct relation?
concepts ki video kab aarhi h
mast video
Thank you 😇🙏
Merge two sorted List -- Leetcode 21
class Solution {
private ListNode mergeTwoSortedList(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val l2.val) {
l2.next = mergeTwoSortedList(l1,l2.next);
return l2;
}
return null;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
return mergeTwoSortedList(list1, list2);
}
}
interview me yadi questions puche to mai bhi interviewer se kahunga "Aao Story Se Code Kre "😁😅
Cool 😅❤️
bhaiya minimum height trees wala question karao plz
Can you please share leetocde link
@@codestorywithMIK meine link diya tha bhej diya but ye dikhai nahi de raha comment mein
Your time complexity calculation is incorrect. It will be O(k*n). This is because you have perform calculation at each leaf here but in case of binary search you do calculation at each node of traversed path.
just using vector property to skip binary search algo
class Solution {
public:
ListNode* mergetwo(ListNode* l1,ListNode* l2){
if(l1==NULL) return l2;
if(l2==NULL) return l1;
if(l1->valval){
l1->next=mergetwo(l1->next,l2);
return l1;
}
else{
l2->next=mergetwo(l1,l2->next);
return l2;
}
}
ListNode* mergeKLists(vector& lists) {
if(lists.size()==0) return NULL;
while(lists.size()>1){
ListNode* new_node=mergetwo(lists[0],lists[1]);
lists.push_back(new_node);
lists.erase(lists.begin());
lists.erase(lists.begin());
}
return lists[0];
}
};
Bhaiya, i thought of this on the first go
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
ListNode* head = NULL;
ListNode* tail = NULL;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
if(list1->val < list2->val){
head = list1;
list1 = list1->next;
}
else{
head = list2;
list2 = list2->next;
}
tail = head;
while(list1 && list2){
if(list1->val < list2->val){
tail->next = list1;
list1 = list1->next;
}
else{
tail->next = list2;
list2=list2->next;
}
tail=tail->next;
}
if(!list1)
tail->next=list2;
else
tail->next=list1;
return head;
}
ListNode* mergeKLists(vector& lists) {
int k = lists.size();
if(k == 0){
return NULL;
}
if(k == 1){
return lists[0];
}
ListNode* res = mergeTwoLists(lists[0], lists[1]);
for(int i = 2 ; i < k ; i++){
res = mergeTwoLists(res, lists[i]);
}
return res;
}
Ye bhi sahi hai na?
Yes it should work too.
I also thought of the exact same solution of iteration in first go 🤜🤛