L24. Flattening a LinkedList | Multiple Approaches with Dry Run 

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

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

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

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

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

Great explanation. Recursive logic illustration is literally gold mine.

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

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

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)

Stack and que ki playlist laooo 😅

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

BHAIYA STACK AND QUEUE KI PLAYLIST LAO❣❣

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

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

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

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.

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

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

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.

You make the hard questions looks so easy 👽

you really takes us forward!

Thank you striver I really needed that recursion logic building

bhaiyaa aaaaaa aaaaaaa STACK QUEUE ki playlist laooooooooooooo

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

❤❤❤❤

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

understood. amazing explanation.

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.

Great explanation and illustration !!!

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

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

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

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?

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

12:39 better approach

v good question

@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

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

topic explation is a like a woww😃

wow. wow

understood

go deep!! go deep!!

great explanation!

Understood, thank you.

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

bro please complete stack heap and string playlist plz

Understood 🎉

Understood!

Understood✅🔥🔥

Awesome.

Thank you Bhaiya

Understood

Thanks

Understoood

Understood:)

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 ?

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

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

woohoo i code the optimal version just by getting intutition

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

Brillant

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.

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

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

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

brute: 00:00 optimal: 12:38

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

at 7:06 😂😂😂

UnderStood

god

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

us

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

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

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

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

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

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

understood

Understood

understood