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
@YogaJournalWithMimansa3 ай бұрын
Amazing explanation! The more I solve these problems, the more I like DSA!! Thanks!!! :)
@abhishekpanda88338 ай бұрын
Great explanation. Recursive logic illustration is literally gold mine.
@alessandrocamilleri12399 ай бұрын
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-oz1dx4 ай бұрын
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
@priyanshuagarwal333616 күн бұрын
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.
@jeetdesaimusic5 ай бұрын
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).
@prajitbanerjee82265 ай бұрын
absolutely correct...you can use similar technique you used while solving k sorted linkedlists..
@ashtonronald3 ай бұрын
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.
@lenovox1carbon6642 ай бұрын
Bro corrected striver now u deserve senior engineer position in Microsoft
@@DURGESHKUMAR-pu4wq ab to karlia bhai ,in 4th year looking for placements. almost saara course hi hogya ab to
@brokegod58713 ай бұрын
@@lifehustlers164 string kaha se kiye? Heap toh lagta hai aditya verma ka dekhe hoge
@studystuff512 ай бұрын
@@lifehustlers164 Me in third year and my college is already having placements, worried about whether I will get placed or not
@stith_pragya7 ай бұрын
#Understood.........Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@sourjadhar93327 ай бұрын
Seeing this explanation i can hence confirm that u r the Recursion GOD man!
@BharathKumarEnishettyАй бұрын
Superrb Lecture,Vey initituive to understand recursive execution contexts, 👌👌👌👌👌👌👌👌👌👌
@Roshanhoro1233 ай бұрын
Best explanation with recursion example.. You explained very well of each step of recursion.How a value is returned when recursion is called. Thanks!!☺
@mohammedharoon11673 ай бұрын
You make the hard questions looks so easy 👽
@RajeevCanDev9 ай бұрын
you really takes us forward!
@harshitjaiswal94398 ай бұрын
understood. amazing explanation.
@robot3.0779 ай бұрын
BHAIYA STACK AND QUEUE KI PLAYLIST LAO❣❣
@juturtaur2982 ай бұрын
Thank you striver I really needed that recursion logic building
@justsomeguywithoutamustach99784 ай бұрын
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.
@harharmahadev31159 ай бұрын
Stack and que ki playlist laooo 😅
@rishikeshjadhav47743 ай бұрын
18:12 it should be list1= list1->child; rare thing for you to go wrong 😅
@romanempire10857 ай бұрын
words by legend - "lets go deep !!" 😂😂😂😂
@kanta44023 ай бұрын
😂😂😂😂
@yashkumar-re3by9 ай бұрын
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)
@divyanshjain79994 ай бұрын
@striver sir pls reply
@akashadak41604 ай бұрын
Exactly
@kanta44023 ай бұрын
Can you tell me how N^2 comes here with an example
@mmbmmbmmbАй бұрын
@@kanta4402 n*(n+1)/2 * m
@dilpreetsingh8815 ай бұрын
Great explanation and illustration !!!
@rohithnarasimhaswaminaidup48746 ай бұрын
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!!
@banothutharun27438 ай бұрын
topic explation is a like a woww😃
@vinay733079 ай бұрын
for this Question , we can use the merge k sorted lists approach using min heap , it is very easy
Iteratively this can also be solved using a Priority Queue (equivalent to recursion stack space) + merging K sorted LLs.
@mahendrachourasiya744410 ай бұрын
Which company can ask this level (very hard) of question? 😅 btw GREAT EXPLANATION.
@helloworld20549 ай бұрын
TCS 😂
@mahendrachourasiya9 ай бұрын
😂
@ugthesep57066 ай бұрын
no man it's medium level question
@talkswithprabh53742 ай бұрын
Asked by Amazon, Microsoft,Goldman sachs
@piyushkumar29003 ай бұрын
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?
@aviraliitianornitian99375 ай бұрын
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.
@ayushaggarwal9064 ай бұрын
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; }
@Crazycaptain32522 күн бұрын
Understood sir
@MJBZG3 ай бұрын
v good question
@SarvanSuthar-d1p2 ай бұрын
I think in brute force approach time complexity should be O(m*n*log(m*n))
@anastasiiamaslova42209 ай бұрын
great explanation!
@vaibhavsingh2886 ай бұрын
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;
@JayVishwakarma2 ай бұрын
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.
@titusandronikus13376 ай бұрын
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-be7hx4 ай бұрын
I think the TC is just O(#nodes). We are actually just touching each node just a few time
@anirudhm1873 ай бұрын
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).
@shubhamjain545199 ай бұрын
12:39 better approach
@NazeerBashaShaik5 ай бұрын
Understood, thank you.
@teqwonnorman492826 күн бұрын
So can it be flattened vertically or horizontally?
@abhinavabhi35685 күн бұрын
Understood
@YourCodeVerse8 ай бұрын
Understood✅🔥🔥
@Learnprogramming-q7f7 ай бұрын
Thank you Bhaiya
@thechetankrishna5 ай бұрын
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 ?
@Lucy927355 ай бұрын
Understood 🎉
@piyushmahale90243 ай бұрын
❤❤❤❤
@KushagraShukla-z6u2 ай бұрын
why we can't merge it from front ? please tell
@BeWarrior-dw4br9 ай бұрын
bhaiyaa aaaaaa aaaaaaa STACK QUEUE ki playlist laooooooooooooo
@Ayeshasingh7202 ай бұрын
understood
@abhishekprasad0103 ай бұрын
Understood!
@Sahilsharma-sk5vr2 ай бұрын
wow. wow
@abhijeetbasfore68169 ай бұрын
Awesome.
@NARUTOUZUMAKI-bk4nx9 ай бұрын
Understoood
@surbhigupta57774 ай бұрын
Understood:)
@vedantnaikwadi53944 ай бұрын
bro please complete stack heap and string playlist plz
@subee1289 ай бұрын
Thanks
@kittupromax9 ай бұрын
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-gf3ci9 ай бұрын
@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_198 ай бұрын
go deep!! go deep!!
@abdulrehmanamer42522 ай бұрын
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
@iamnoob75937 ай бұрын
Brillant
@ravipatel-xu5qi6 ай бұрын
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.
@chiraggill29404 ай бұрын
try to code /dry run it once you will get your answer
@dhruvkhanna24103 ай бұрын
Optimized code is working for only 2 test cases out of 15........
@ayushindapure69036 ай бұрын
7:04 I didn't catch that as well🤣
@ishanmoykhede94843 ай бұрын
woohoo i code the optimal version just by getting intutition
@hetvikasari78285 ай бұрын
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); } }