L24. Flattening a LinkedList | Multiple Approaches with Dry Run

[@ankit_yadav11]

you are the first teacher who have courage to dry run the whole process of how recursion is happenning here , salute you sir u made me understand each and every word of this problem u r the legend

[@YogaJournalWithMimansa]

Amazing explanation! The more I solve these problems, the more I like DSA!! Thanks!!! :)

[@abhishekpanda8833]

Great explanation. Recursive logic illustration is literally gold mine.

[@alessandrocamilleri1239]

Very good explanation. Striver uses a recursive solution which is fine as it is important to brush up on recursion from time to time. For completeness sake this is the iterative solution, which is trivial. The merge function is common to both solutions and is not included. Node* flattenLinkedList(Node* head) { if(head == NULL) return head; Node* head2 = head; while (head2->next) { Node* temp = head2; head2 = head2->next; temp->next = NULL; head = mergeLL (head, head2); } return head; }

[@shantanugupta-oz1dx]

You are a god. So much stress I have while solving problems. But If I search for the problem and I find TUF has solved it. I know that no matter what by the end of the video I'll understand it in full depth. Thank you so much

[@priyanshuagarwal3336]

The TC for the optimal approach comes out to be O(N*N*M). Proof: Suppose an average length of M for each vertical list, Then the first merge operation will be: M+M = 2M, Second merge operation will be M+2M(because list size increasing) = 3M the merge operations will go like: 4M, 5M, .....up to N*M summation of which will be N*N*M Or we can also see a worse case if our last list contains N/2 elements and then all other list contains just 1 element, in that case also we can see the TC to be N*N*M complexity. Correct me if I am wrong. Better approach would be to use a priority_queue.

[@jeetdesaimusic]

According to me,the time complexity will be like : 2M(for merging last 2 lists) + 3M(for merging last 2 combined and last 3rd) + 4M + ... + NM, taking M common, M(2+3+....N) , which is approximately, M(N)(N+1)/2 = O(M*N^2).

[@prajitbanerjee8226]

absolutely correct...you can use similar technique you used while solving k sorted linkedlists..

[@ashtonronald]

I think you claim this due to the fact that the size of the final merged list used for backtracking keeps increasing. It is logical & hence correct.

[@lenovox1carbon664]

Bro corrected striver now u deserve senior engineer position in Microsoft

[@rahulnegi4027]

nah bro it should be O(n*mlog(n*m))

[@lifehustlers164]

stack & queue leaao aur strings (basic & medium) please

[@aayushgakhar3525]

yes

[@DURGESHKUMAR-pu4wq]

Aa gaya bhai😮

[@lifehustlers164]

@@DURGESHKUMAR-pu4wq ab to karlia bhai ,in 4th year looking for placements. almost saara course hi hogya ab to

[@brokegod5871]

@@lifehustlers164 string kaha se kiye? Heap toh lagta hai aditya verma ka dekhe hoge

[@studystuff51]

@@lifehustlers164 Me in third year and my college is already having placements, worried about whether I will get placed or not

[@stith_pragya]

#Understood.........Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@sourjadhar9332]

Seeing this explanation i can hence confirm that u r the Recursion GOD man!

[@BharathKumarEnishetty]

Superrb Lecture,Vey initituive to understand recursive execution contexts, 👌👌👌👌👌👌👌👌👌👌

[@Roshanhoro123]

Best explanation with recursion example.. You explained very well of each step of recursion.How a value is returned when recursion is called. Thanks!!☺

[@mohammedharoon1167]

You make the hard questions looks so easy 👽

[@RajeevCanDev]

you really takes us forward!

[@harshitjaiswal9439]

understood. amazing explanation.

[@robot3.077]

BHAIYA STACK AND QUEUE KI PLAYLIST LAO❣❣

[@juturtaur298]

Thank you striver I really needed that recursion logic building

[@justsomeguywithoutamustach9978]

really great question, I did it with minHeap first. Your solution is really intriguing. There is no need for recursion though, we can iteratively merge from the head of our original linkedlist as well. Just keep a pointer for the next upcoming linkedlist in a variable called front.

[@harharmahadev3115]

Stack and que ki playlist laooo 😅

[@rishikeshjadhav4774]

18:12 it should be list1= list1->child; rare thing for you to go wrong 😅

[@romanempire1085]

words by legend - "lets go deep !!" 😂😂😂😂

[@kanta4402]

😂😂😂😂

[@yashkumar-re3by]

time complexity galat hai bhai. aapne N x O(2 M) liya hai but wo har baar O(2 M) nhi hoga sirf first time hoga. it will be 2M + 3M + 4M +.... + NM = O(M x N^2)

[@divyanshjain7999]

@striver sir pls reply

[@akashadak4160]

Exactly

[@kanta4402]

Can you tell me how N^2 comes here with an example

[@mmbmmbmmb]

@@kanta4402 n*(n+1)/2 * m

[@dilpreetsingh881]

Great explanation and illustration !!!

[@rohithnarasimhaswaminaidup4874]

There is a small mistake in the psuedo code in merge function you wrote list1=list1-next instead of list1->child; by the way the dry run and everything were perfect. Thanks!!

[@banothutharun2743]

topic explation is a like a woww😃

[@vinay73307]

for this Question , we can use the merge k sorted lists approach using min heap , it is very easy

[@biovolt222]

Can you share the solution if possible?

[@mansipatel3481]

@@biovolt222 Node flatten(Node root) { // Your code here PriorityQueue pq = new PriorityQueue((a,b)->a.data-b.data); Node temp=root; while(temp!=null){ pq.offer(temp); temp=temp.next; } Node dummy=new Node(-1); temp=dummy; while(!pq.isEmpty()){ Node node = pq.poll(); if(node.bottom!=null){ pq.offer(node.bottom); } temp.bottom=node; temp=temp.bottom; } return dummy.bottom; }

[@parthverma2436]

Iteratively this can also be solved using a Priority Queue (equivalent to recursion stack space) + merging K sorted LLs.

[@mahendrachourasiya7444]

Which company can ask this level (very hard) of question? 😅 btw GREAT EXPLANATION.

[@helloworld2054]

TCS 😂

[@mahendrachourasiya]

😂

[@ugthesep5706]

no man it's medium level question

[@talkswithprabh5374]

Asked by Amazon, Microsoft,Goldman sachs

[@piyushkumar2900]

Can we use a priority queue to store the pointers and then pick the minimum one and iterate it with the second minium in the queue, NMlog(N) maybe?

[@aviraliitianornitian9937]

striver i think we dont need the linr in this question "if(dumynode)dumynode->child->next=null;" because it already covered in the loop the code will work without this line.

[@ayushaggarwal906]

that line is better if we use iteration. Like this Node* flat(Node* first, Node* second, Node* third){ Node* dummy= new Node(-1); Node* mover=dummy; Node* temp1=first; Node* temp2=second; while(temp1!=NULL && temp2!=NULL){ if(temp1->datadata){ mover->child=temp1; mover=temp1; temp1=temp1->child; } else{ mover->child=temp2; mover=temp2; temp2=temp2->child; } } if(temp1!=NULL){ mover->child=temp1; } else{ mover->child=temp2; } dummy->child->next=third; // Using this line return dummy->child; } Node* flattenLinkedList(Node* head) { Node* temp=head; if(temp->next==NULL) return temp; while (temp->next != NULL) { temp=flat(temp, temp->next, temp->next->next); } return temp; }

[@Crazycaptain325]

Understood sir

[@MJBZG]

v good question

[@SarvanSuthar-d1p]

I think in brute force approach time complexity should be O(m*n*log(m*n))

[@anastasiiamaslova4220]

great explanation!

[@vaibhavsingh288]

Test cases 29/30 Your time complexity: O(n^2logn) We think Common causes of Time Limit Exceeded : Your time complexity: O(n^2logn)

[@rahulnegi4027]

@takeUforward wanted to point out the worst time complexity would be O(n*mlog(n*m)) as we are mergin at each step and at worse they both can be of same length please do correct me if i am wrong see yah

[@DeadPoolx1712]

UNDERSTOOD;

[@JayVishwakarma]

12:29 the space comp. should be O(n*m) beacuse the new Linkedlist is created in order to return the answer so it is not counted as a space comp.

[@titusandronikus1337]

the final time complexity is incorrect, it’s actually quadratic. But there’s a way to make it linearithmic: you need to merge lists in pairs and then results of those pairs and so on

[@AdityaKumar-be7hx]

I think the TC is just O(#nodes). We are actually just touching each node just a few time

[@anirudhm187]

In recursion approach the space complexity we took was O(N) as recursion stack but will we not consider the N dummyNodes we created while we merged 2 lists? We could have deleted / freed them before we return from function, otherwise our SC is O(2N).

[@shubhamjain54519]

12:39 better approach

[@NazeerBashaShaik]

Understood, thank you.

[@teqwonnorman4928]

So can it be flattened vertically or horizontally?

[@abhinavabhi3568]

Understood

[@YourCodeVerse]

Understood✅🔥🔥

[@Learnprogramming-q7f]

Thank you Bhaiya

[@thechetankrishna]

Recursive Solution is partially accepted on Coding Ninjas platform. 29/30. Solution with Extra Space i.e. List is accepted 30/30. Any optimisation required in recursive solution ?

[@Lucy92735]

Understood 🎉

[@piyushmahale9024]

❤❤❤❤

[@KushagraShukla-z6u]

why we can't merge it from front ? please tell

[@BeWarrior-dw4br]

bhaiyaa aaaaaa aaaaaaa STACK QUEUE ki playlist laooooooooooooo

[@Ayeshasingh720]

understood

[@abhishekprasad010]

Understood!

[@Sahilsharma-sk5vr]

wow. wow

[@abhijeetbasfore6816]

Awesome.

[@NARUTOUZUMAKI-bk4nx]

Understoood

[@surbhigupta5777]

Understood:)

[@vedantnaikwadi5394]

bro please complete stack heap and string playlist plz

[@subee128]

Thanks

[@kittupromax]

Sir, can we solve this question using priority queue? Like we did in merging K linked list . here is my solution of the question using linked list but the solution is not getting accepted on coding ninjas struct mycomp { bool operator()(Node* a, Node* b){ return a->data > b->data; } }; Node* flattenLinkedList(Node* root){ priority_queue p; while (root != NULL) { p.push(root); root = root->next; } Node* dummy=new Node(-1); Node* temp=dummy; while (!p.empty()) { auto k = p.top(); p.pop(); temp->child=k; temp=temp->child; if (k->child) p.push(k->child); } return dummy->child; }

[@AS-gf3ci]

@kittupromax very good observation!! This approach should work just fine and TC & SC won't vary much using a min heap. So this could well be an accepted approach for this problem.

[@divyansh_19]

go deep!! go deep!!

[@abdulrehmanamer4252]

You can avoid recursion stack space O(n) by making an iterative solution The overall time complexity would be O(n*m) and the space complexity would be O(1) Here is my code: class Solution: def flatten(self, root): #Your code here res = Node(float('-inf')) while root: res = self.merge2Lists(root, res) root = root.next return res.bottom def merge2Lists(self, l1, l2): temp = Node(-1) res = temp while l1 and l2: if l1.data

[@iamnoob7593]

Brillant

[@ravipatel-xu5qi]

why can't we use priority queue concept to merge multiple sorted linked list concept. Here all vertical list are sorted. Simply add head of each vertical list in priority queue and then process their respective child node.

[@chiraggill2940]

try to code /dry run it once you will get your answer

[@dhruvkhanna2410]

Optimized code is working for only 2 test cases out of 15........

[@ayushindapure6903]

7:04 I didn't catch that as well🤣

[@ishanmoykhede9484]

woohoo i code the optimal version just by getting intutition

[@hetvikasari7828]

please tell me why this code is not passing 1 test case out of 30 - /* Node(int data, Node next, Node child) { this.data = data; this.next = next; this.child = child; } }*/ public class Solution { public static Node merging(Node list1 , Node list2){ Node dommy = new Node(0) , result = dommy; while ( list1 != null && list2 != null ){ if(list1.data < list2.data){ result.child = list1; result = list1; list1 = list1.child; }else { result.child = list2; result = list2; list2 = list2.child; } result.next = null; } if(list1 != null ) result.child = list1; else result.child = list2; if (dommy.child != null) { dommy.child.next = null; } return dommy.child; } public static Node flattenLinkedList(Node head) { if(head == null || head.next == null ) return head; Node merged_head = flattenLinkedList(head.next); return merging( head , merged_head); } }

[@hitmanop4078]

brute: 00:00 optimal: 12:38

[@saimurali9648]

at 7:06 😂😂😂

[@alpha_motivation8967]

not get sorted linkedlist by optimal approach

[@AkashKumarTiwary-u4b]

god

[@rahulhembram4519]

UnderStood

[@YeaOhYeahh]

using priority queue, (approach explained in next video) ``` Node* flattenLinkedList(Node* head) { if(!head) return NULL; priority_queue pq; Node* dummy = new Node(-1); Node* temp = head; while(temp != NULL) { pq.push({temp -> data, temp}); temp = temp -> next; } temp = dummy; while(pq.size()) { auto it = pq.top(); pq.pop(); if(it.second -> child) pq.push({it.second -> child -> data, it.second -> child}); temp -> child = it.second; temp = it.second; temp -> next = NULL; } return dummy -> child; } ```

[@mansipatel3481]

Java Solution using PriorityQueue (similar to merge k sorted list): Node flatten(Node root) { // Your code here PriorityQueue pq = new PriorityQueue((a,b)->a.data-b.data); Node temp=root; while(temp!=null){ pq.offer(temp); temp=temp.next; } Node dummy=new Node(-1); temp=dummy; while(!pq.isEmpty()){ Node node = pq.poll(); if(node.bottom!=null){ pq.offer(node.bottom); } temp.bottom=node; temp=temp.bottom; } return dummy.bottom; }

[@dayashankarlakhotia4943]

Node flatten(Node head){ if(head==null||head.next==null) return head; head.next =flatten(head.next); return merge(head,head.next); } Node merge(Node cur1,Node cur2){ if(cur1==null) return cur2; if(cur2==null) return cur1; Node ans=null; if(cur1.data

[@cenacr007]

us

[@cenacr007]

Working Coding Ninjas Code if someone else is also getting runtime error: Node* merge(Node* list1, Node* list2) { Node* dummyNode = new Node(-1); Node* res = dummyNode; while(list1 != NULL && list2 != NULL) { if(list1->data < list2->data) { res->child = list1; res = list1; list1 = list1->child; } else { res->child = list2; res = list2; list2 = list2->child; } res->next = nullptr; } if(list1) { res->child = list1; } else { res->child = list2; } if(dummyNode->child) { dummyNode->child->next = nullptr; } res->child->next = nullptr; // this line will get rid of that error return dummyNode->child; } Node* flattenLinkedList(Node* head) { if(head == NULL || head->next == NULL) { return head; } Node* mergedHead = flattenLinkedList(head->next); head = merge(head, mergedHead); return head; }

[@rakeshdhingra9253]

Thanks

[@Satvik__Jain]

O(NlogN) Node *flatten(Node *root) { // Your code here multimap mpp; Node* temp = root, *bot = root; while(temp){ while(bot){ mpp.insert({bot->data, bot}); bot = bot->bottom; } temp = temp -> next; bot = temp; } auto it = mpp.begin(); auto nxt = mpp.begin(); while(it != mpp.end()){ // nxt++; // (it->second)->next = nxt->second; // it++; cout first

[@ajml_hnter]

Easy Approach in C++ Space Complexity: O(1) Time Complexity: O(n*2m) Node* mergeLists(Node* root1, Node* root2){ Node* dummy = new Node(0); Node* head = dummy; while(root1 && root2){ if(root1->data < root2->data){ head->child = root1; root1 = root1->child; }else{ head->child = root2; root2 = root2->child; } head = head->child; } if(root1) head->child = root1; if(root2) head->child = root2; return dummy->child; } Node* flattenLinkedList(Node* head){ Node* prev = NULL; while(head){ prev = mergeLists(prev, head); head = head->next; } return prev; }

[@franciskp9117]

Hey guys....I've got a better approach. It's running on VSCODE, but not working on Coding Ninjas platform. " Node* flattenLinkedList(Node* head) { Node* temp = head; while(temp->next != NULL){ Node* top = temp->next; temp->next = temp->child; while(temp->child != nullptr){ temp = temp->next; temp->next = temp->child; } temp->next = top; temp = top; } temp->next = nullptr; return head; }"

[@vishious14]

The nodes are supposed to be connected as child and not next. There is an explanation at the end of problem statement.

[@shreyxnsh.14]

Bruteforce code: Node* flattenLinkedList(Node* head) { // Write your code here Node* temp = head; vector vec; while(temp){ Node* child = temp; while(child){ vec.push_back(child->data); child=child->child; } temp=temp->next; } if(vec.size()==0) return NULL; sort(vec.begin(), vec.end()); Node* newhead = new Node(vec[0]); Node* mover = newhead; for(int i=1;ichild = temp; mover=mover->child; } return newhead; }

[@AkOp-bf9vm]

ITERATIVE WAY class Solution { public: // Function which returns the root of the flattened linked list. Node* merger(Node*h1,Node*h2){ if(h1==NULL) return h2; if(h2==NULL) return h1; Node* dummy= new Node(-1); Node* mover=dummy; while(h1 && h2){ if(h1->datadata){ mover->bottom=h1; mover=h1; h1=h1->bottom; } else{ mover->bottom=h2; mover=h2; h2=h2->bottom; } } if(h1){ mover->bottom=h1; } if(h2){ mover->bottom=h2; } return dummy->bottom; } Node *flatten(Node *root) { // Your code here if(root==NULL || root->next==NULL) return root; Node*head1=root; Node*curr=NULL; while(head1){ curr=merger(head1,curr); head1=head1->next; } return curr; } };

[@kaushalpadaliya529]

understood

[@dewanandkumar8589]

Understood

[@hardikpatel352]

understood

[@lakhansingh_barod]

Understood