L24. Flattening a LinkedList | Multiple Approaches with Dry Run
Вставка
- Опубліковано 1 жов 2024
- Problem Link: tinyurl.com/2p...
Entire LL Sheet: takeuforward.o...
Check our A2Z DSA Course: takeuforward.o...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/take...
18:12 it should be list1= list1->child;
rare thing for you to go wrong 😅
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
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
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).
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))
Amazing explanation! The more I solve these problems, the more I like DSA!! Thanks!!! :)
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 and que ki playlist laooo 😅
bhaiyaa aaaaaa aaaaaaa STACK QUEUE ki playlist laooooooooooooo
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.
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
BHAIYA STACK AND QUEUE KI PLAYLIST LAO❣❣
Great explanation. Recursive logic illustration is literally gold mine.
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!!
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
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;
}
words by legend - "lets go deep !!" 😂😂😂😂
😂😂😂😂
Test cases
29/30
Your time complexity: O(n^2logn)
We think Common causes of Time Limit Exceeded :
Your time complexity: O(n^2logn)
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;
}
I think in brute force approach time complexity should be O(m*n*log(m*n))
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?
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);
}
}
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
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
Superrb Lecture,Vey initituive to understand recursive execution contexts, 👌👌👌👌👌👌👌👌👌👌
@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
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
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........
#Understood.........Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Seeing this explanation i can hence confirm that u r the Recursion GOD man!
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 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
So can it be flattened vertically or horizontally?
go deep!! go deep!!
bro please complete stack heap and string playlist plz
woohoo i code the optimal version just by getting intutition
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).
12:39 better approach
You make the hard questions looks so easy 👽
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 ?
Iteratively this can also be solved using a Priority Queue (equivalent to recursion stack space) + merging K sorted LLs.
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.
❤❤❤❤
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;
}
```
why we can't merge it from front ? please tell
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
Best explanation with recursion example.. You explained very well of each step of recursion.How a value is returned when recursion is called. Thanks!!☺
I think the TC is just O(#nodes). We are actually just touching each node just a few time
understood. amazing explanation.
Thank you striver I really needed that recursion logic building
brute: 00:00
optimal: 12:38
v good question
you really takes us forward!
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;
at 7:06 😂😂😂
understood
understood
7:04 I didn't catch that as well🤣
wow. wow
Great explanation and illustration !!!
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, thank you.
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.
topic explation is a like a woww😃
Understood:)
Understood!
Understood 🎉
Understood
understood
god
us
UnderStood
Understood✅🔥🔥
Thank you Bhaiya
Understoood
Brillant
great explanation!
Understood
Awesome.
Thanks
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;
}