Add Two Numbers Given as LinkedLists | Amazon | Microsoft | Facebook | Qualcomm

[@takeUforward]

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

[@elements8630]

understoood thanks

[@harshitrathi3077]

Yea

[@amishasahu1586]

Understooooooooooooooooooood!!

[@sunnykumarpal9679]

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.

[@ankitr2969]

that's the tip, don't let interviewer know that u have already solved the problem. 😂

[@Jaydeeeeeeep]

What if they saw my leetcode profile?😂

[@sanskarsinghiit]

😂😂

[@lohithreddy4628]

thats a greta tbh😂😂

[@GeekyBaller]

I was asked this question in my interview with Amazon. Great work, Raj bhaiya!

[@shivamverma9447]

Hi, can you help me

[@dutt_2302]

this problem can be solved without any create new node. O(1) - space complexity

[@trmpsanjay]

@@dutt_2302 yes by creating two pointer head and tail method

[@muktadirkhan6674]

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

[@muktadirkhan6674]

@@trmpsanjay Its a singly linked list, what are you going to achieve by a tail pointer?

[@avishekroy1642]

your way of teaching is very simple, and easy to understand

[@settyruthvik6236]

#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

[@mrinmoyaus761]

Great placement series is hitting bro just watching everytime i open youtube.

[@abhay9994]

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

[@tanishq2766]

I solved this without any extra space, making the additions in the node itself, was a bit complicated but yet it worked !

[@avadheshsingh4255]

You are amazing best programming teacher on youtube keep it up brother

[@DeepakGupta-zz1vf]

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

[@muktadirkhan6674]

Yeah saw this approach on the LeetCode solution.

[@prabaljain5887]

i was solving this question on leetcode and the logic hit me in just 2mins but i wasn't able to code it

[@hrishitsarkar6388]

Striver You are GREAT !!!!! Love from West Bengal

[@NagaVijayKumar]

Thank you bro.. For uploading multiple videos in a single day..

[@hemanthvarmas]

Nicely put explanation (as always) for "how to add two numbers given as Linked Lists". Thanks bro.

[@dhruvrajput5194]

Finally a question i figured out myself😂

[@reallydarkmatter]

You are really amazing at explaining every concept clearly

[@Metalrave]

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?

[@aakashgupta7211]

We should try not to make any changes to the input provided.

[@GameZone-yd8kr]

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

[@tanishq2766]

oh alright@@aakashgupta7211

[@vishalrane1439]

bhai ekdam simple karke bataya, Thanks bro

[@gamingwithhemend9890]

Love your simple and clean explanation 💯💯📸

[@techdemy4050]

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.

[@aravinds6406]

Well Explained

[@deepgajjar5275]

we can optimize space complexity by first calculating the sum and then using old linked list nodes to create a sum linked list

[@Raju_Sharma852]

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.

[@ujjwalgupta518]

Now I have the clearity on this question...thx ❤️

[@jatinkumar4410]

Nice and clear explanation. One question... Should we consider the space used by output list when calculating space complexity?

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@priyankarai7005]

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)

[@takeUforward]

No you cannot as it us said dont destroy the given lists.

[@laxminarayanchoudhary939]

@@takeUforward Thank you clearing, Same O(1) space complexity came in my mind.

[@shri9229]

intresting point anyways

[@kaichang8186]

understood, thanks for the detail explanation

[@Karan-vq5vg]

Amazing video...cleared all the doubts

[@ritikashishodia675]

Great bhaiya... U always inspiration..... I am stuck in that problem.... Thanks to give idea and approach I am appreciate and to u always

[@SudhanshuKumar-lp1nr]

Why do we need the dummy node in the starting why can't directly start from first sum value?

[@manishmotwani3744]

That #striver sir for providing such a wonderful content. It helps me a lot!!

[@willturner3440]

I think your approach better but not most optimized one Brother what if the interviewer say add without reversing

[@DeepakLalchandaniProfile]

How do you add without reversing ??? 😅😅😅

[@princepavan-ip1lg]

Awesome explaination sir ji👏👏👏👏

[@adarshurmaliya9901]

Great Explanation 👍

[@-ShangsitNath]

Can we optimise the space by modifying anyone of the linked list and returning the head of that linked list ??

[@28_vijayadityarajr12]

lovely vedio

[@ankitbhatt5630]

Good Explanation!

[@aryansinha1818]

8:22 C++ Code

[@amansingh.h716]

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 .

[@nabilafzal2984]

Awesome explanation ..thanks Bhaiya

[@ashdeepsingh6785]

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.

[@sourabhchoudhary7289]

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.

[@Nikhil-qd9up]

OPTIMAL - We can also do it inplace without taking a dummy linkedlist

[@freshcontent3729]

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

[@Nikhil-qd9up]

@@freshcontent3729 no bro he is correct,what i said was doing it inplace

[@freshcontent3729]

@@Nikhil-qd9up but bro doing inplace is optimal right ? as it is way better . cause we aint using space.

[@Nikhil-qd9up]

@@freshcontent3729 yes bro

[@freshcontent3729]

@@Nikhil-qd9up so in interview which one should i tell ?

[@itsugo_]

Thank you!

[@AKD4536]

Amazing explanation

[@GurpreetSingh-ps6kl]

thank you

[@amanjot3492]

Good solution

[@shashankgsharma0901]

Understood!

[@aditik2233]

understood Thank you

[@gautamsuthar4143]

It took me time but I wrote the code exactly same as you did.

[@freshcontent3729]

bro but this can be done without extra space also right ? that is withought making a whole new linked list ( the sum one )

[@wog4299]

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

[@riaria5982]

sum += carry; carry=sum/10; Isn't it butcher the sum value? It should be: carry= sum/10 sum = sum+ carry;

[@abhirajtyagi9244]

Nice sir je👌👌

[@cossMania]

Thanks man

[@bhagyashri7729]

can we do it in single temp node and avoid having 2 dummy pointers?

[@krishnavamsichinnapareddy]

Understood 🔥

[@exdee8446]

Why are we checking if (carry == 1) for loop's termination?

[@p0tat0627]

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

[@PranathNaik]

nice explaination

[@sakshamsrivastava6280]

hands down !!

[@praharshsingh2095]

What is the significance of using dummy pointer ?

[@ajvindersingh6835]

JUST TO STORE THE ADDRESS OF FIRST NODE😉

[@achinttrivedi4667]

​@@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 ?

[@kishanyadav-ob4xl]

Thanks sir

[@pranayghosh7912]

bhaia what is the difference betweeen striver n take u forward did u stopped striver?

[@RM-lb7xw]

Great video bro, keep it up 👌

[@subhajeetchakraborty1791]

understoooood

[@indhumathi5846]

understood

[@aakashSky-0]

There would be a memory leak in this for dummy. So make sure you delete it at the end before returning.

[@aakashdabas9490]

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!

[@coding6409]

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

[@pratikshadhole6694]

awesome bhai

[@elements8630]

nice video.

[@fatehpreetsingh1440]

gem

[@ankitnegi4802]

instead of || there should be && in while loop condition ...please clear it am i right or not??

[@neerajmahapatra5239]

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

[@surajsah3361]

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.

[@tejaspatel2212]

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

[@avishekroy1642]

great content

[@pragyavyas186]

We can do it without using the extra space also.

[@takeUforward]

That will be destroying the original list, which is not allowed, also since you returning the answer which is taking space, it is okay!

[@syedyaseenabbasrizvi8072]

Can you please tell the intuition behind this approach..?

[@takeUforward]

Its a simple algo, why do you need intuition. Isn’t it straightforward to add them like that, simple maths stuff!

[@syedyaseenabbasrizvi8072]

@@takeUforward Alright got it..thanku

[@rohankrishnani]

please solve it without using space one time, i tried and am stuck with one testcase

[@freshcontent3729]

bro but this can be done without extra space also right ? that is withought making a whole new linked list ( the sum one )

[@karangoyal7386]

Bhaiya I was dropper but not selected should I go for local college in my city

[@neerajyadav2349]

Java Code class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry=0; ListNode dummy=new ListNode(0,null); ListNode temp=dummy; while(l1!=null || l2!=null || carry!=0){ int ival=l1!=null?l1.val:0; int jval=l2!=null?l2.val:0; int sum = ival+jval+carry; ListNode node=new ListNode(sum%10); carry=sum/10; temp.next=node; temp=temp.next; if(l1!=null){ l1=l1.next; } if(l2!=null){ l2=l2.next;} } return dummy.next; } }

[@tekken1935]

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?

[@amansinghal4663]

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

[@surbhigupta5777]

US

[@amanchandok685]

When do you plan to finish this series?

[@gandhijainamgunvantkumar6783]

Understooooooooooooooood

[@yashas3567]

can u make a video for the same question if head points to the most significant digit

[@sudheerg9182]

then you need to reverse both list and do the same as explained

[@yashchandan7313]

Thankyouu!

[@rohitgpt7201]

hmmmmmm

[@yashchandan7313]

@@rohitgpt7201 😂 😂

[@om_1_2]

Got it bro👍👍

[@hy-ti1ic]

Wow 😍

[@shouvikdatta6831]

Thnx vai❤

[@mohdkhaleeq7468]

on take you forward website space complexity is written O(max(m,n)) and you said O(n) it is confusing

[@aryansingh7101]

O(max(m,n)) will return the maximun of size od n or m, so it can be O(n) or O(m)

[@preetitripathi6280]

This solution is giving wrong answer for some test cases.What should be other edge cases which should be taken into consideration?

[@GameZone-yd8kr]

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 😍

[@prashantraj6366]

Can 1 of 2 linked list be used instead of dummy node? If not, then why not?

[@EntEduRealm]

kzbin.info/www/bejne/naHKZ2B6hMmfrtk watch this if you dont understand

[@neerajmahapatra5239]

Unable to understand what are you asking for

[@p0tat0627]

U can't change the input list, also it is not recommended to modify the input data structure

[@jaysaxena185]

Bro, your c++ solution is very nice but lc giving time limit exceeded while submission of c++ code, please help in optimizing this. Thanks

[@takeUforward]

The code explained was an accepted solution, cross check for typos or some extra lines that you would have added..

[@sparks8754]

yes, it is showing TLE on leetcode

[@jayachandra677]

Thank you bhai!

[@curiousMe1000]

Why we need the dummy nood in the beginning?

[@saketkumar7335]

kindly compile and run this code also

[@takeUforward]

Its an accepted code that I explain :)

[@ghoshdipan]

Why is it that I'm not able to solve it optimally!

[@willturner3440]

Bhaiya what if the interviewer says add two list without reversing it?

[@chetanpatil2473]

Not understanding anything

[@avishekroy1642]

please make more videos

[@takeUforward]

I am making..

[@nitingupta1417]

can't it be done in O(1) space complexity

[@takeUforward]

then you have to reuse the given linkedlist only, which is not advisable..

[@nitingupta1417]

@@takeUforward understoood... and thanks for your reply 😁

[@devinenisowmya1479]

@@takeUforward can u explain why it is not advisible

[@nitingupta1417]

@@devinenisowmya1479 becasue the input linked list will get distorted... sometimes we are not allowed to modify the inputs...

[@SatyamKumar-dj3jo]

why carry is always 1? carry can be zero, right?

[@neerajmahapatra5239]

Yes it can be 0