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

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

[@JJ-tp2dd]

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); } }

[@shweta1013]

You are just awesome !!.. Cant believe i wrote the code myself after listening to this video !!

[@guptajiivlogging8174]

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)

[@souravjoshi2293]

Same bro

[@nawazthezaifre8870]

placement hoa kya bhai ??

[@22gauravkumar70]

@@nawazthezaifre8870 placement hua?

[@akshaychavan5511]

This question felt hard for me when I initially attempted it. But, now it feels quite easy.

[@gui-codes]

too good man. becoming your fan day by day. One stop for revision

[@souravjoshi2293]

I think you are the best who can make things easier like a cake walk

[@ShivaaySingh20]

Thank you so much bhai for making this question very easy to understand 🙌❤.

[@vineetkumar2899]

awesome bhaiya😍

[@tutuimam3381]

Amazing explanation🌹

[@atifhu]

Bhai kya smjhate ho❤️❤️

[@RohitYadav-uo6uo]

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?

[@zgodgaming857]

the best explanation

[@shabananoor9423]

Best explanation

[@utkarshpatel949]

very good explanation pls make video on today leetcode contest questions

[@codestorywithMIK]

I will soon start those as well . Just trying to make plans as per my time management. Soon

[@Methre_]

very nice bhai;

[@mudassarnazar1663]

You are genius ,

[@priyanshudubey2245]

Bhaiya weekly contests ke questions par bhi video bana dijiye please.

[@codestorywithMIK]

I will soon start those as well . Just trying to make plans as per my time management. Soon

[@nihalsingh6233]

Thank You soo much sir !! You really made it easy

[@codestorywithMIK]

I am so glad it helped ❤️❤️❤️

[@elakstein]

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.

[@codestorywithMIK]

Indeed

[@alphadrones23]

yup.. we could use the iterative approach to merge the two lists

[@Whirlwind03]

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; }

[@JJ-tp2dd]

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); } }

[@saisathvikreddyloka7578]

🔥🔥

[@ishwarkokkili7646]

Masterful !!

[@codestorywithMIK]

Thank you so much 🙏❤️😇

[@khushijain3574]

you explained so nicely keep making such videos

[@codestorywithMIK]

Thank you so much 😇🙏

[@khushijain3574]

@@codestorywithMIK please create video on quick sort on linked list , i want your approach to solve this thanks

[@user-qz4wk1mb5m]

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?

[@surajsidar3280]

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.

[@shivamjadon2257]

mast video

[@codestorywithMIK]

Thank you 😇🙏

[@harshlakra3260]

concepts ki video kab aarhi h

[@ShivaaySingh20]

interview me yadi questions puche to mai bhi interviewer se kahunga "Aao Story Se Code Kre "😁😅

[@codestorywithMIK]

Cool 😅❤️

[@MakeuPerfect]

bhaiya minimum height trees wala question karao plz

[@codestorywithMIK]

Can you please share leetocde link

[@MakeuPerfect]

@@codestorywithMIK meine link diya tha bhej diya but ye dikhai nahi de raha comment mein

[@AshishSharma-tf3fy]

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]; } };

[@drbullah1388]

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?

[@codestorywithMIK]

Yes it should work too.

[@harsh.jain22]

I also thought of the exact same solution of iteration in first go 🤜🤛

[@yashsharma1774]

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.