Merge k Sorted Lists | EP 14

Lecture Notes:
Watch the complete Linked List Series • Linked List Series
Crio.Do
Get 10% discount Crio.do www.crio.do/redeem/7aef353
Question (codestudio) bit.ly/3CwTxDc
Question (leetcode) leetcode.com/problems/merge-k...
Placement Preparation Roadmap • Roadmaps for Placement
Hi, I am Fraz.
I am Software Engineer working at Curefit and I love teaching.
This is my Channel where I upload content related to Interviews and my personal experiences.
My contact details
Instagram :- / frazmohammad
Connect with me on LinkedIn :- / mohammad-f-bb4886157
Telegram Group t.me/LeadCoding

[@chahatnagar1536]

You've explained it so clearly! I was stuck on this question for a very long time. Thank you so much!

[@mohammadfraz]

🔥 keep watching

[@amanpandey4550]

I tried with my own and my logic was correct but i failed to implement. I watched many videos but u cleared all my doubts. Thank u.

[@bhavyagupta1389]

Your linked list series is amazing!!!

[@mohammadfraz]

Thanks ❤️😊

[@raghvendrakhatri5848]

Lect - 16 completed, sir love♥️ the way you explain each and every concept, please keep creating such wonderful content 💯 your playlist are helping me alot in understanding the topics and improving my skills. Thankyou bhaiya ♥️

[@AmanChauhan-hr1wh]

I was thinking in same way but had difficulty in writing code for same...but u made it clear thank you so much

[@abhi36292]

great clean and concise code,Thanks

[@technicalteam3298]

you have such a great explanation

[@stith_pragya]

Thank You So Much Fraz Brother for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@AmarjeetKumar-en1gk]

Thanks for the comparator function explanation.

[@panavkumar9009]

Please make the next playlist on heap. That is one tough topic to understand.

[@user-jw9bt1nl7k]

I think the TC is O(n*k log k) lets say each list has 'n' nodes. to merge them we need n*k and to perform the divide and conquer part we need 'log k'

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@Music-tp8gg]

Badhiya kaam krte ho faraz bhai

[@ashishkashyap1872]

Amazing explanation

[@jatingupta3443]

Completed till this lecture

[@nimeshsingh6229]

nicely explained bhaiya !

[@surajbaranwal56.]

Amazing playlist

[@aditiranjan303]

Hard problem ko kitni easily solve kar dia😀

[@asifhasan7444]

very good explanation

[@I_Dont_Care_2bh]

Brute Force:- Here, we are just storing all nodes sorted in 'multimap' then just construct a new List. (According to Fraz Bhaiya's 1st Approach) for naive approach refer this video.... #CODE:- class Solution { public: ListNode* mergeKLists(vector& lists) { multimapm; for(auto &it : lists){ ListNode *head = it; while(head){ m.insert(pair{head->val, head}); head = head->next; } } ListNode *dummy = new ListNode(-1); ListNode *tail = dummy; for(auto &it : m){ tail->next = it.second; tail = it.second; } return dummy->next; } };

[@pranaykumar9433]

comparator mein a->valval hota na

[@ratnasanjay]

Thankyou bhaiya for this video

[@shamimsarker839]

Alhamdulillah, solved it by myself.

[@kartikking7]

bhaiya, comparator function mei a->val > b->val kyu aaya hai instead of a->valval, as we want it sorted in increasing order?

[@shubhamkumar_noob_cs-go_pl581]

why do we need a custom opearatorm while the deafault one greater is already available to use?

[@sadashivshinde9150]

Can we avoid cmp function by using priority_queue ?

[@ankit_yadav11]

bhaiya every linkedlist ke 1st node ko kaise acces kar rhe ho aap list[i] karke . like hmko aisa same q ek tha merge sorted arrays to hmlog usme row and col store karke access karte the to pta lag pata tha ki alag alag array ka first element access kar rhe hai but yha kaise pta karenge withour row number ke kaise pta lagega ab dusra linkedlist aa gya only i use karke kaise ho rha yha

[@sagarbora7768]

can we use simple global function instead of comparator class

[@nitinkumarsingh7959]

nice, everything is clear.

[@mohammadfraz]

Thanks

[@saptarshimajumdar180]

thank you

[@BobMarley-qh2qs]

bhai at 17:52 if we do ListNode* temp = q.top(); wouldn''t it be pointing to the whole list rather than a single element ? for example temp=q.top() / [1,3,4] how would it be pointing to a single element? and wouldn't the end result be: after everything done it would be like >> tail->[1,4,5]->[1,3,4]->[2,6]->[3,4]->[4,5]->[4]->[5]->[6] when it should be like >> tail->1->1->2->3->4->4->5->6;

[@lakshaydubey3281]

sir can we just insert all the elements of list on min heap and the keep extracting the min element until the head becomes null

[@ishuchaudhary4502]

How priority queue working here??Does it takes each element of linked list or only firsrt element of each linked list inside for loop ??can you pls explain q.push(v[i]) how this thing working inside priority queue

[@satyamshukla1418]

bhaiya please make video on comparators pls also your content on linkedlist is helping me a lot in my understanding of the concepts._/\_.

[@Manish_Sahu]

nice explanation

[@rsp8053]

Got doubt cleared

[@Shivamkumar-xu6hu]

Very well explained 🔥

[@mohammadfraz]

Thanks

[@Shivamkumar-xu6hu]

@@mohammadfraz thanks to u bhaiya 🔥

[@ianujkumark]

appreciate it

[@kartikkumar-6009]

i think divide and conquer is better approach for this or we can say merge sort

[@SoHmmShorts]

bhaiya compirator wala samajh nhi wala ..wo kahase parhu ? or uske liye kya refer karu ? plz help if anyone also know . thanks in advance

[@SunnyGupta00]

Reach++🔥

[@BTECE_manichandT]

@fraz bhayya pls explain why (a->val > b->val )instead of (a->val < b->val)??

[@tarunkumar.d8379]

Hi , Priority queue me sabse phele niche se fill hota hai, like low Priority Wale first fill hote hain, so agar a.val is greater than b.val ,that means uska prirority low hai, toh hum usse phele insert karne keliye return true karthe hain.

[@manojg4451]

bro, waiting for more videos. Please do more videos

[@parasjaggi268]

great

[@tech_wizard9315]

By what date, entire series will be uploaded

[@mohammadfraz]

Bro please jo hua hai vo dekh lo.

[@ani68]

Sir when we do q.push(lists[i]) how only the first value of each list is pushed ??🤔🤔🤔🤔🤔🤔🤔🤔

[@inFamous16]

Actually... initial vector that is passed to the function contains heads of all those k lists and once we have head, we can traverse the lists right? It is just that leetcode not shown this clearly in the problem statement itself, but it is a common sense thing.

[@sageoustheory1957]

if(temp->next != NULL) pq.push(temp->next); what is the purpose oif this line

[@pritishpattnaik4674]

bhai I have a doubt , min heap ke syntax mein toh hum greater pass karwa sakte hai in place of that comparator function ? please clarify

[@talkwithrd5697]

I think if we pass greater then it won't give us correct answer, comparator function will work fine

[@shashikalwar1853]

@@talkwithrd5697 why so as result do not depend upon syntax

[@inFamous16]

It is because ListNode* stores the address, not the values itself and how do you compare addresses?

[@BTECE_manichandT]

@@inFamous16 it should be a->val < b->val na??pls explain

[@inFamous16]

@@BTECE_manichandT In C++ STL (by default) the largest element is at the top (i.e. at the last position), so that whenever we do pq.top(), we get highest priority element at first. Hence we have to do 'a->val > b->val' to get a min heap

[@mdnadeem6343]

🔥🔥🔥🔥🔥

[@mohammadfraz]

Thanks

[@niranjanraje7160]

what if we push all the nodes in min heap and then keep poping out the minimum ??

[@inFamous16]

as ListNode* is address type, by default the priority_queue is not going to sort them based on the address. We then have to push the values and then recreate linked_list from those values... but we have to do this in-place

[@jitishgupta6424]

time complexity and SC at 12:30

[@himanshugupta7647]

Bhaiya product based company direct service based se hire karti h kya

[@mohammadfraz]

Yes why not

[@shreyanshjain4781]

bhiya please share your LinkedIn link , amazing explanation ,how bhiya you are you are able to think lots of approach , but i am not able to think more then 1-2 optimise solution approach

[@ritikgupta1133]

practice

[@ritikgupta1133]

see his leetcode profile you will be amazed that he has solve more then 1500 questions. nothing beats practice

[@jaikrishan9100]

sir .TC ,SC kaise aaya samjh nahi aaya kuch.

[@aayushojha3088]

we are inserting lisits[i] , isse to poora linked list insert hoga na ? but hame to bas 1st node insert krna thana ?

[@tarunkumar.d8379]

Lists of i me sirf head pointer of that list hai bro, hum kabhi bhi pura LL pass nhi karthe, only the pointers are passed.

[@naziyakhan4096]

All about Linkedlist I have understood is Curr node,next node, next.next node Return something is by default false I am not understanding anything I have come this far watching linkedlist, Where m I going wrong I am trying so much to understand But I am not understanding itself what is actually happening What to doo😢

[@MdFaisal-kj1ck]

Nice

[@mohammadfraz]

Thanks Faisal

[@MdFaisal-kj1ck]

Kab aayega sir next ep?

[@mohammadfraz]

Aagae hain

[@kkumar07]

v[i] kya hai

[@Sonu-tg6tg]

Please make videos using JAVA

[@jenil151]

18:10 can someone explain why we are pushing next of temp back in queue since temp will always be top element of queue

[@BTECE_manichandT]

we want to compare the minimum element right ..so we push in to the heap until the next node is nullptr

[@krishshah5162]

cmp vala nhi smja kyu bnaya hai!?

[@desihiphop4998]

Bhaiya 1 number bas heap ni aata tha search kiya phir hogya !!!!!!!

[@mohammadfraz]

Niiice, yahi karna hota hai bro ❤️

[@apurvtripathi7185]

What is Time & Space Complexity ? ' class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy ; while(l1 != null && l2 != null){ if(l1.val

[@awwtawnoo]

class Solution { private: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; if (l1->val > l2->val) swap(l1, l2); ListNode *res = l1; while (l1 != nullptr && l2 != nullptr) { ListNode *temp = nullptr; while (l1 != nullptr && l1->val val) { temp = l1; l1 = l1->next; } temp->next = l2; swap(l1, l2); } return res; } public: ListNode *mergeKLists(vector &lists) { if (lists.empty()) return nullptr; int k = (int)(lists.size()); while (k > 1) { for (int i = 0; i < k / 2; i++) { lists[i] = mergeTwoLists(lists[i], lists[k - 1 - i]); } k = (k + 1) / 2; } return lists.front(); } }; not using heap, but better solution than just merging two consecutive ListNode-s from the ListNode vector

[@tarunkumar.d8379]

Hi bro mujhe yeh smjh nhi ah rha hai ki lists front me kese answer agaya??

[@awwtawnoo]

@@tarunkumar.d8379 In every iteration we are taking two lists and merging them to form the bigger list, at the end of all the iterations we need to return the HEAD of the finally formed list which is lists.front( )

[@tarunkumar.d8379]

@@awwtawnoo I'll have to dry run , we save the space complexity in this solution so I gotta knw this one.

[@awwtawnoo]

@@tarunkumar.d8379 Deffo, also my personal advice is follow Striver's LinkedList series along with this series, you'll get to know best approaches from both the playlists.

[@tarunkumar.d8379]

@@awwtawnoo yes but he doesn't have merge k lists video, but hey I made a dry run an understood now how we get answer at 0 index, but how is it different from the first approach where we merger two lists then, merge tye resultant list with third list and so on?? And how TC is Log k?

[@dailydestress6189]

Bhai tum sab content creator sse request hai ki CRIO jaise company ko promote krna band kar do. They legit spam call me every week or so for registering in their program even when i am not interested.

[@ShyamalDas-kd5vt]

Bade bade code mein Chhota Chhota error hote rehte Hain😅🤪