Understooooooooooooooood? . Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thank you bhaiya for making such videos . which ever topic i feel hard i try to find your videos. Your videos are really fabulous . Please be making such videos.
@@dutt_2302 You would have to create a single node if the carry is there at the last node. And btw the solution Striver explained is also O(1). The space isnt counted for the variables we need to return.
I wanted to send you a heartfelt thank you for your tireless dedication to teaching DSA for free. Your selflessness and passion for helping students with their job interview preparation have made a significant impact on my life and countless others. I am incredibly grateful for the knowledge and confidence you have imparted to us. Thank you for everything you do!❣✨✨
#code in python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, A: Optional[ListNode], B: Optional[ListNode]) -> Optional[ListNode]: l3=ListNode(0) head=l3 carry=0 while A or B or carry: if A: carry += A.val A=A.next if B: carry += B.val B=B.next l3.val=carry%10 carry=carry//10 if A or B or carry: l3.next=ListNode(0) l3=l3.next return head
I was able to do this in O(1) space as well with some optimisation (adding the sum values in the given listnodes only). Wouldn't that be a better answer to give to an interviewer?
It was a really awesome explanation if you don't mind can you make a video on " k Queues in a single array " and " k Stack in a single array " when you START WITH STACK and QUEUE because I am not able to understand these two questions.
Yeah, i did the same while solving this problem. But we should not temper the input files/lists untill and unless we are allowed to do so. Better ask the interviewer whether modification to the input files is allowed or not.
can someone pls explain me why are we checking for carry == 0 and exiting if carry is 0. It is possible that we add two numbers like 2+3 it wont generate carry and yet the list can continue to have more numbers.
iS THIS CORRECT BRUTEFORCE WHAT I AM THINKING if we Store these 2 link list in string then reverse it then parse this in INTEGER and then sum it and then again store this in string and then reverse it , and at last iterate it create new nodes link them .
instead of creating a new list we can just put the sum of every corresponding nodes in the nodes of the lists itself. Space complexity becomes from O(n) to O(1)
@@ajvindersingh6835 @take U forward but where we are storing the address of first node can you explain please? and why we are returning dummy's next ?
cause consider an example two list l1, l2 having only single digits, 8 & 7. If u sum it up u get 15. U add 5 to the new_list, the carry 1 gets ignored if u consider only l1 and l2 cause in the next loop l1 & l2 both null, but u still have 1 as carry left. Thats why carry should also be considered for the loop going..
It's the inbuilt implementation of leetcode for evaluation. Here, in leetcode when you return dummy.next, it will return the whole node same goes for return head. Hope this helps :)
Actually && will be be for stopping the while loop. But in while loop we are writing condition that should move the while loop... If any one of them is satisfied means if either n1 is not null or n2 is not null or carry is not 0 we have to move... It's not like if all of them satisfy then we have to move... Just say it in English you will get to know either we have to use && or ||
why u did ' || ' not ' && ' : why this, while(l1 != NULL || l2 != NULL || carry!=0 ) not while(l1 != NULL && l2 != NULL && carry!=0 ) We have to check untill each of the l1 becomes NULL. Please answer sir!
@@freshcontent3729 on which lists will you stored l1 or l2 , and how will you find which is greater and if the sum exceeds the list then again you will have to add a new Node which I guess taking a new list is great instead of modifying the given list
Striver Bhaiya, do you think that having such SDE sheets, interviewer might explicitly look at the questions in such SDE sheets and not repeat these particular questions?
exactly what i am thinking.... interviewers also know that nowadays everyone is doing these sde sheets so they will definitely not ask questions present in it
@@factfactorial632 rather just store it in one of the two linked lists regardless of the size and once that reaches NULL, let the last pointer point to the first element of the 2nd linked list and then store it in that list. This way u will not have to traverse the length of the linked list to check which one is longer
Understooooooooooooooood?
.
Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/
.
.
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
understoood thanks
Yea
Understooooooooooooooooooood!!
Thank you bhaiya for making such videos . which ever topic i feel hard i try to find your videos. Your videos are really fabulous . Please be making such videos.
that's the tip, don't let interviewer know that u have already solved the problem. 😂
What if they saw my leetcode profile?😂
😂😂
thats a greta tbh😂😂
I was asked this question in my interview with Amazon.
Great work, Raj bhaiya!
Hi, can you help me
this problem can be solved without any create new node.
O(1) - space complexity
@@dutt_2302 yes by creating two pointer head and tail method
@@dutt_2302 You would have to create a single node if the carry is there at the last node. And btw the solution Striver explained is also O(1). The space isnt counted for the variables we need to return.
@@trmpsanjay Its a singly linked list, what are you going to achieve by a tail pointer?
your way of teaching is very simple, and easy to understand
Great placement series is hitting bro just watching everytime i open youtube.
I wanted to send you a heartfelt thank you for your tireless dedication to teaching DSA for free. Your selflessness and passion for helping students with their job interview preparation have made a significant impact on my life and countless others. I am incredibly grateful for the knowledge and confidence you have imparted to us. Thank you for everything you do!❣✨✨
I solved this without any extra space, making the additions in the node itself, was a bit complicated but yet it worked !
#code in python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, A: Optional[ListNode], B: Optional[ListNode]) -> Optional[ListNode]:
l3=ListNode(0)
head=l3
carry=0
while A or B or carry:
if A:
carry += A.val
A=A.next
if B:
carry += B.val
B=B.next
l3.val=carry%10
carry=carry//10
if A or B or carry:
l3.next=ListNode(0)
l3=l3.next
return head
You are amazing best programming teacher on youtube keep it up brother
Striver You are GREAT !!!!! Love from West Bengal
Thank you bro..
For uploading multiple videos in a single day..
Love your simple and clean explanation 💯💯📸
Nicely put explanation (as always) for "how to add two numbers given as Linked Lists". Thanks bro.
You are really amazing at explaining every concept clearly
i was solving this question on leetcode and the logic hit me in just 2mins but i wasn't able to code it
Now I have the clearity on this question...thx ❤️
I was able to do this in O(1) space as well with some optimisation (adding the sum values in the given listnodes only). Wouldn't that be a better answer to give to an interviewer?
We should try not to make any changes to the input provided.
That's My Nigg@ !
I did that too !
Kinda Noob Solution but u get the 💡 :
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ans = l1,*prev;
int carry = 0;
while(l1 && l2){
int sum = l1->val+l2->val+carry;
if(sum > 9){
carry = 1;
l1->val = sum-10;
}
else{
carry = 0;
l1->val = sum;
}
prev = l1;
l1 = l1->next;
l2 = l2->next;
}
if(carry){
prev->next = l1 ? l1 : l2;
while(l1){
int sum = l1->val+carry;
if(sum > 9){
carry = 1;
l1->val = sum-10;
}
else{
carry = 0;
l1->val = sum;
}
prev = l1;
l1 = l1->next;
}
while(l2){
int sum = l2->val+carry;
if(sum > 9){
carry = 1;
l2->val = sum-10;
}
else{
carry = 0;
l2->val = sum;
}
prev = l2;
l2 = l2->next;
}
if(carry){
ListNode *node = new ListNode(carry);
prev->next = node;
}
}
else
prev->next = l1 ? l1 : l2;
return ans;
}
};
oh alright@@aakashgupta7211
we can also do like while(l1!=null || l2!=null) and after loop we can check if carry>0 then make a node else dont make
Yeah saw this approach on the LeetCode solution.
bhai ekdam simple karke bataya, Thanks bro
It was a really awesome explanation if you don't mind can you make a video on " k Queues in a single array " and " k Stack in a single array " when you START WITH STACK and QUEUE because I am not able to understand these two questions.
Well Explained
Thank you very much. You are a genius.
Nice and clear explanation. One question... Should we consider the space used by output list when calculating space complexity?
Amazing video...cleared all the doubts
Awesome explaination sir ji👏👏👏👏
Great bhaiya... U always inspiration..... I am stuck in that problem.... Thanks to give idea and approach I am appreciate and to u always
Finally a question i figured out myself😂
understood, thanks for the detail explanation
Why do we need the dummy node in the starting why can't directly start from first sum value?
Great Explanation 👍
That #striver sir for providing such a wonderful content. It helps me a lot!!
we can optimize space complexity by first calculating the sum and then using old linked list nodes to create a sum linked list
Yeah, i did the same while solving this problem. But we should not temper the input files/lists untill and unless we are allowed to do so. Better ask the interviewer whether modification to the input files is allowed or not.
Can we optimise the space by modifying anyone of the linked list and returning the head of that linked list ??
can someone pls explain me why are we checking for carry == 0 and exiting if carry is 0. It is possible that we add two numbers like 2+3 it wont generate carry and yet the list can continue to have more numbers.
Good Explanation!
Awesome explanation ..thanks Bhaiya
I think your approach better but not most optimized one
Brother what if the interviewer say add without reversing
How do you add without reversing ??? 😅😅😅
iS THIS CORRECT BRUTEFORCE WHAT I AM THINKING
if we Store these 2 link list in string then reverse it then parse this in INTEGER and then sum it and then again store this in string and then reverse it , and at last iterate it create new nodes link them .
if list are not given in rev oreder then brute can be to make int out of linked list then Add them both and make new linked list of ans integer.
Great video bro, keep it up 👌
instead of creating a new list we can just put the sum of every corresponding nodes in the nodes of the lists itself. Space complexity becomes from O(n) to O(1)
No you cannot as it us said dont destroy the given lists.
@@takeUforward Thank you clearing, Same O(1) space complexity came in my mind.
intresting point anyways
bhaia what is the difference betweeen striver n take u forward did u stopped striver?
Nice sir je👌👌
lovely vedio
can we do it in single temp node and avoid having 2 dummy pointers?
Thank you!
understood Thank you
What is the significance of using dummy pointer ?
JUST TO STORE THE ADDRESS OF FIRST NODE😉
@@ajvindersingh6835 @take U forward but where we are storing the address of first node can you explain please?
and why we are returning dummy's next ?
Amazing explanation
8:22 C++ Code
Why are we checking if (carry == 1) for loop's termination?
cause consider an example two list l1, l2 having only single digits, 8 & 7. If u sum it up u get 15. U add 5 to the new_list, the carry 1 gets ignored if u consider only l1 and l2 cause in the next loop l1 & l2 both null, but u still have 1 as carry left. Thats why carry should also be considered for the loop going..
I have a doubt, when we are returning dummy.next why it is returning whole node and why not the single node of dummy.next.
It's the inbuilt implementation of leetcode for evaluation. Here, in leetcode when you return dummy.next, it will return the whole node same goes for return head.
Hope this helps :)
bro but this can be done without extra space also right ? that is withought making a whole new linked list ( the sum one )
nice explaination
in c++ why you are returning the next of the dummy node we could direct start from the starting of the linked list
instead of || there should be && in while loop condition ...please clear it am i right or not??
Actually && will be be for stopping the while loop. But in while loop we are writing condition that should move the while loop... If any one of them is satisfied means if either n1 is not null or n2 is not null or carry is not 0 we have to move... It's not like if all of them satisfy then we have to move... Just say it in English you will get to know either we have to use && or ||
Good solution
Understood 🔥
why u did ' || ' not ' && ' : why this, while(l1 != NULL || l2 != NULL || carry!=0 ) not while(l1 != NULL && l2 != NULL && carry!=0 )
We have to check untill each of the l1 becomes NULL.
Please answer sir!
if you use an && then this code will not work if the linked lists are not equal, using an || takes consideration of that edge case
It took me time but I wrote the code exactly same as you did.
bro but this can be done without extra space also right ? that is withought making a whole new linked list ( the sum one )
@@freshcontent3729 on which lists will you stored l1 or l2 , and how will you find which is greater and if the sum exceeds the list then again you will have to add a new Node which I guess taking a new list is great instead of modifying the given list
thank you
Thnx vai❤
Striver Bhaiya, do you think that having such SDE sheets, interviewer might explicitly look at the questions in such SDE sheets and not repeat these particular questions?
exactly what i am thinking.... interviewers also know that nowadays everyone is doing these sde sheets so they will definitely not ask questions present in it
sum += carry;
carry=sum/10;
Isn't it butcher the sum value?
It should be:
carry= sum/10
sum = sum+ carry;
Thanks man
on take you forward website space complexity is written O(max(m,n)) and you said O(n) it is confusing
O(max(m,n)) will return the maximun of size od n or m, so it can be O(n) or O(m)
Got it bro👍👍
great content
We can do it without using the extra space also.
That will be destroying the original list, which is not allowed, also since you returning the answer which is taking space, it is okay!
Can 1 of 2 linked list be used instead of dummy node? If not, then why not?
ua-cam.com/video/gpg6-DOdlxw/v-deo.html watch this if you dont understand
Unable to understand what are you asking for
U can't change the input list, also it is not recommended to modify the input data structure
Can you please tell the intuition behind this approach..?
Its a simple algo, why do you need intuition. Isn’t it straightforward to add them like that, simple maths stuff!
@@takeUforward Alright got it..thanku
please solve it without using space one time, i tried and am stuck with one testcase
Bro, your c++ solution is very nice but lc giving time limit exceeded while submission of c++ code, please help in optimizing this. Thanks
The code explained was an accepted solution, cross check for typos or some extra lines that you would have added..
yes, it is showing TLE on leetcode
nice video.
Bhaiya I was dropper but not selected should I go for local college in my city
Why we need the dummy nood in the beginning?
hands down !!
can't it be done in O(1) space complexity
then you have to reuse the given linkedlist only, which is not advisable..
@@takeUforward understoood... and thanks for your reply 😁
@@takeUforward can u explain why it is not advisible
@@devinenisowmya1479 becasue the input linked list will get distorted... sometimes we are not allowed to modify the inputs...
can u make a video for the same question if head points to the most significant digit
then you need to reverse both list and do the same as explained
Understood!
Thanks sir
When do you plan to finish this series?
Sir can u give the link of the doc file which u showed in starting of this video PLs
Google “striver sde sheet”
There would be a memory leak in this for dummy. So make sure you delete it at the end before returning.
Why this condition is used in while loop
Carry ==1
Can anyone explain please
Thankyouu!
hmmmmmm
@@rohitgpt7201 😂 😂
Bhaiya ye btaiye ki c++ ds algo kahan se crein
This solution is giving wrong answer for some test cases.What should be other edge cases which should be taken into consideration?
Check my Constant Space Solution (C++) : 😘😘
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ans = l1,*prev;
int carry = 0;
while(l1 && l2){
int sum = l1->val+l2->val+carry;
if(sum > 9){
carry = 1;
l1->val = sum-10;
}
else{
carry = 0;
l1->val = sum;
}
prev = l1;
l1 = l1->next;
l2 = l2->next;
}
if(carry){
prev->next = l1 ? l1 : l2;
while(l1){
int sum = l1->val+carry;
if(sum > 9){
carry = 1;
l1->val = sum-10;
}
else{
carry = 0;
l1->val = sum;
}
prev = l1;
l1 = l1->next;
}
while(l2){
int sum = l2->val+carry;
if(sum > 9){
carry = 1;
l2->val = sum-10;
}
else{
carry = 0;
l2->val = sum;
}
prev = l2;
l2 = l2->next;
}
if(carry){
ListNode *node = new ListNode(carry);
prev->next = node;
}
}
else
prev->next = l1 ? l1 : l2;
return ans;
}
};
It Passes All test Cases and is pretty Efficient 😍
Why is it that I'm not able to solve it optimally!
Wow 😍
OPTIMAL - We can also do it inplace without taking a dummy linkedlist
but then why did striver say that this is the only optimal solution do this problem ? is he wrong ? please help me i am confused
@@freshcontent3729 no bro he is correct,what i said was doing it inplace
@@Nikhil-qd9up but bro doing inplace is optimal right ? as it is way better . cause we aint using space.
@@freshcontent3729 yes bro
@@Nikhil-qd9up so in interview which one should i tell ?
Bhaiya what if the interviewer says add two list without reversing it?
Hiee. is Space complexity o(n)? isnt max(m,n)? please clarify
ua-cam.com/video/gpg6-DOdlxw/v-deo.html watch this if you dont understand
understoooood
why carry is always 1? carry can be zero, right?
Yes it can be 0
awesome bhai
I have a question how dummy's next is pointing to head?
ua-cam.com/video/gpg6-DOdlxw/v-deo.html watch this if you dont understand
how dummy -> next is giving the answer, can anyone tell me pls
How about using one of the two linked lists( greater length) to store the answer. In that way we even save space.
yes i have did like that..it worked
bro it will increase time complexity on the other hand becuse we will have to figure it out which one is greater
@@factfactorial632 rather just store it in one of the two linked lists regardless of the size and once that reaches NULL, let the last pointer point to the first element of the 2nd linked list and then store it in that list. This way u will not have to traverse the length of the linked list to check which one is longer
kindly compile and run this code also
Its an accepted code that I explain :)