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
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).
Just want to add that this is worst case time complexity: Every element in the last list is smaller than the smallest in the second-to-last list, Every element in the second-to-last list is smaller than the smallest in the third-to-last list, and so on. This forces a full iteration through each list during merging, leading to maximum time complexity. In the best case (Striver time complexity), the lists are sorted in ascending order from first to last: Merging the last two lists takes O(M) since the second-to-last list is exhausted first, leaving only the last list to append. Similarly, merging the third-to-last list with the previous result also takes O(M), and so on.
Just by understanding the idea of merging that you explained at 21:00, i am able to solve the problem with no failed testcases. Thanks Striver for excellent way of teaching.
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.
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
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; }
Thanks bro your course has helped me so much I was able to solve this problem on my own and I am feeling great love you bhai.❤...You are the God of DSA👑🔥
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!!
Best explanation with recursion example.. You explained very well of each step of recursion.How a value is returned when recursion is called. Thanks!!☺
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.
If you are getting confused or not comfortable with recursion, you can merge lists from starting instead of end with a while loop(merging two adjacent lists). Easy Haiiiiii! Node *flatten(Node *root) { Node * head = root ; Node * curr = root -> next ; while(curr) { head = mergeLists(head , curr) ; curr = curr -> next ; } return head ; }
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)
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
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.
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
@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
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).
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 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.
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; }
@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.
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!!! :)
Great explanation. Recursive logic illustration is literally gold mine.
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).
absolutely correct...you can use similar technique you used while solving k sorted linkedlists..
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.
Bro corrected striver now u deserve senior engineer position in Microsoft
nah bro it should be O(n*mlog(n*m))
Just want to add that this is worst case time complexity:
Every element in the last list is smaller than the smallest in the second-to-last list,
Every element in the second-to-last list is smaller than the smallest in the third-to-last list, and so on.
This forces a full iteration through each list during merging, leading to maximum time complexity.
In the best case (Striver time complexity), the lists are sorted in ascending order from first to last:
Merging the last two lists takes O(M) since the second-to-last list is exhausted first, leaving only the last list to append.
Similarly, merging the third-to-last list with the previous result also takes O(M), and so on.
Iteratively this can also be solved using a Priority Queue (equivalent to recursion stack space) + merging K sorted LLs.
Just by understanding the idea of merging that you explained at 21:00, i am able to solve the problem with no failed testcases. Thanks Striver for excellent way of teaching.
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.
stack & queue leaao aur strings (basic & medium) please
yes
Aa gaya bhai😮
@@DURGESHKUMAR-pu4wq ab to karlia bhai ,in 4th year looking for placements. almost saara course hi hogya ab to
@@lifehustlers164 string kaha se kiye? Heap toh lagta hai aditya verma ka dekhe hoge
@@lifehustlers164 Me in third year and my college is already having placements, worried about whether I will get placed or not
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
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;
}
This iterative solution is wrong as it breaks the link between the successive node pairs....
Here's the correct version: -
Node *flatten(Node *head) {
if(head==NULL || head->next==NULL)
return head;
Node* prev = head, *nxt = head;
while(head->next!=NULL) {
prev = head;
head = head->next;
nxt = head->next;
head = mergeLinkedLists(head, prev);
head->next = nxt;
}
return head;
}
Thanks bro your course has helped me so much I was able to solve this problem on my own and I am feeling great love you bhai.❤...You are the God of DSA👑🔥
words by legend - "lets go deep !!" 😂😂😂😂
😂😂😂😂
🌚🌚
cringe
finished the playlist in 4 days thanks a lot striver
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!!
#Understood.........Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Seeing this explanation i can hence confirm that u r the Recursion GOD man!
Best explanation with recursion example.. You explained very well of each step of recursion.How a value is returned when recursion is called. Thanks!!☺
for this Question , we can use the merge k sorted lists approach using min heap , it is very easy
Can you share the solution if possible?
@@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;
}
18:12 it should be list1= list1->child;
rare thing for you to go wrong 😅
You make the hard questions looks so easy 👽
Stack and que ki playlist laooo 😅
BHAIYA STACK AND QUEUE KI PLAYLIST LAO❣❣
Superrb Lecture,Vey initituive to understand recursive execution contexts, 👌👌👌👌👌👌👌👌👌👌
you really takes us forward!
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.
If you are getting confused or not comfortable with recursion, you can merge lists from starting instead of end with a while loop(merging two adjacent lists). Easy Haiiiiii!
Node *flatten(Node *root) {
Node * head = root ;
Node * curr = root -> next ;
while(curr) {
head = mergeLists(head , curr) ;
curr = curr -> next ;
}
return head ;
}
Thank you striver I really needed that recursion logic building
Which company can ask this level (very hard) of question? 😅
btw GREAT EXPLANATION.
TCS 😂
😂
no man it's medium level question
Asked by Amazon, Microsoft,Goldman sachs
understood. amazing explanation.
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)
@striver sir pls reply
Exactly
Can you tell me how N^2 comes here with an example
@@kanta4402 n*(n+1)/2 * m
Great explanation and illustration !!!
topic explation is a like a woww😃
these last 2 question were pretty challenging!
Lecture successfully completed on 01/12/2024 🔥🔥
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
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.
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;
}
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.
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?
12:39 better approach
❤❤❤❤
I think in brute force approach time complexity should be O(m*n*log(m*n))
great explanation!
Test cases
29/30
Your time complexity: O(n^2logn)
We think Common causes of Time Limit Exceeded :
Your time complexity: O(n^2logn)
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
I think the TC is just O(#nodes). We are actually just touching each node just a few time
bhaiyaa aaaaaa aaaaaaa STACK QUEUE ki playlist laooooooooooooo
Understood✅🔥🔥
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
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).
thank you bhai
Understood, thank you.
Understood 😀
Understood sir
So can it be flattened vertically or horizontally?
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 ?
Thank you Bhaiya
Understood 🎉
7:04 I didn't catch that as well🤣
UNDERSTOOD;
wow. wow
understood!!!
Awesome.
bro please complete stack heap and string playlist plz
why we can't merge it from front ? please tell
28-1-25
Thanks
Understoood
go deep!! go deep!!
understood
Understood!
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.
try to code /dry run it once you will get your answer
Understood:)
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;
}
@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.
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;
}
```
Brillant
Understood
at 7:06 😂😂😂
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);
}
}
woohoo i code the optimal version just by getting intutition
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
UnderStood
14:15
not get sorted linkedlist by optimal approach
the first solution does not really go through all the child nodes
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
god
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;
}
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
us
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;
}
Thanks
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;
}"
The nodes are supposed to be connected as child and not next. There is an explanation at the end of problem statement.
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
Understood