3 Sum (LeetCode 15) | Full solution with examples and visuals | Interview Essential

[@butteredtequilla9046]

You have just gained a subscriber. Out of all videos, this is so far the most comprehensible explanation. Thank you kind sir!!

[@nikoo28]

Welcome aboard! Your feedback and love is much appreciated. Keeps me motivated :D

[@ZachDift-kc4nk]

did this code work when you submitted it on leetcode?

[@butteredtequilla9046]

@@ZachDift-kc4nk I can’t remember honestly it was a long time ago

[@ngm-oe8ow]

If you sort the array the complexity becomes O(nLog(n)) in the 2 sum part and you said the complexity becomes o(n), but for the 3sum sorting is okay because you are reducing it to o(n^2). The explanation was quite good and understandable thanks.

[@peasantfaye5403]

It's not like you sort an array n times in sum2, however. You sort an array once, then you iterate through it in O(n) time. You could say it's O(n + log(n)), but it's still linear time, so we simplify it to O(n).

[@ngm-oe8ow]

With the inbuilt sorting or any sorting algorithm it would take O(nlog(n)) not O(log(n)) time. so O(nlog(n)+n)) simplifies to O(nlog(n)). so it's not linear time. it would take linear time if you use hashing.

[@peasantfaye5403]

True, my bad.@@ngm-oe8ow

[@bobaGogo]

@@peasantfaye5403 you can only solve 2 sum in O(n) with a hashmap. If you do the 2 pointer solution you will get a O(1) space complexity, but O(n*log(n)) time complexity.

[@GaganSingh-zz9el]

why nlogn time complexity in 2sum using 2 pointer @@bobaGogo

[@RakshithVrishab-ht8vk]

Simple ,yet optimized , thanks Nikhil!

[@anoopghildiyal6413]

At 5:30 how the time complexity is O(n)?? you have sorted the array so it would be O(nlogn) already for the sorting so how it would be O(n) for total algorithm??

[@SRC_ARENA]

Using a HashMap, the complexity for TwoSum will be O(N). Without sorting only it can be done.

[@AyushSharma-vq5ix]

i think the same thing, TC should be O(nlogn) + O(n) , SC= O(n)

[@AaliyahJohnson-d6c]

Best explanation I've watched. Thank you!

[@nikoo28]

Awesome, thank you!

[@jbr.1]

I liked your way of teaching. Subscribed!!

[@nikoo28]

I'm glad you liked it. More videos coming soon!

[@yadavom2001]

Beautifully explained 😊

[@Satya-g5t]

Really appreciate the effort you put into making other people understand. It is great service.

[@architagarwal7379]

Time complexity is O[n^2logn]. We have to use hashmap apprach of 2 sum if the array is not sorted by default

[@nikoo28]

O(n^2) will be dominant

[@NIGHTSHADE123]

@@nikoo28 we are sorting the array so complexity should be 0(n2 logn)

[@benji-t7v]

I think sorting us just done once so nsquared + logn which reduces to n2

[@ShahidHussain-dh3pg]

Amazing explanation. You redefined the meaning of comprehensive😎

[@NeelakshiSachdeva]

Girl did 2 sum and 3 sum today!! Keep going, faang is waiting for me

[@nikoo28]

You can do it!

[@YorozuyaNeesan2010]

Thank you very much for your clear explanations and for drawing things out.

[@michaeljohnbritto8399]

thanks for your fantastic explaination with simple code.

[@gayiii1911]

Thankyou sir, great explanation i understood very well

[@AbhishekKumar-hi8oj]

very nice explanation, before that i went through couple of video to understand properly but this time I understood . Thanks.

[@nikoo28]

glad I could help

[@imdarkseid2343]

you did well soldier,nice approach simple and elegant but the duplicates numbers in arrays has to skipped to increase the faster execution

[@FnuAdnan]

Waouh, I was really lost with that problem but you explained it so well that I understand now. Thanks!

[@checkraiser100]

Damn, this video made the problem super easy

[@samridhshubham8109]

Very Excellent solution, was stuck in this prob for hrs

[@nikoo28]

glad I could help

[@Dadu-g4r]

Amazing explanation 🔥

[@nikoo28]

Thank you 🙌 😄

[@shabanafirdose4671]

Too good , Thank you for sharing your knowledge

[@nikoo28]

glad i could help you!!

[@hinocenciopaulo]

Best approach.

[@viveknamdev2605]

Thanks Sir For Solution

[@SanskrutiKanse]

Well explained❤ helpful!!!!

[@nicedoodly6392]

one of the best KZbinr

[@sysybaba420]

great explanation, congratulations on putting in this effort!!!

[@nikoo28]

Glad you enjoyed it!

[@oknokok]

Nice explanation, setup and video quality 📸

[@MadhavanMan]

The code takes 672 Runtime.Whether it is optimal

[@IndianHistoryInDetails]

Using Hashet increases the time a lot we are gettinh 800 ms execution time. we can use below to reduce it. class Solution { public List threeSum(int[] nums) { if(nums.length

[@ghayoorhussain8930]

Crystal Clear Explanation Sir

[@plutomessi21]

thank you bhaiya , i was stuck in this since yesterday

[@Mano_Vikas]

You said, for viola in between at 5:22. What does that mean? Just curious

[@nikoo28]

Means kind of ‘wow’ as an exclamation

[@rukhsanakhan9542]

dil se pyaar aapko sir

[@supershinobi7892]

your explanation is awesome thank you brother i was not able to solve this question before your video Now i solved.

[@nikoo28]

You are most welcome

[@melk48111]

Great work Nikhil

[@sumitkaranjkar3819]

what about edge cases like all +ve or all -ve or all 0 where you have to return {}, {}, {0,0,0} respectively

[@venkateshdhanasekaran5398]

After seeing lot many videos, finally I found the crystal clear approach.. Thank you so much brother. One question, how you handle the duplicate element in this?

[@nikoo28]

I am using a HashSet, that takes care of duplicates

[@karthikmalode-ir5tw]

Great solution ..understandable

[@purnimahianl5678]

You explain very well 👏

[@jataman123]

How does this solution ensures that we don't use one value multiple times?

[@nikoo28]

because all 3 pointers point at different indexes

[@mayankkumargiri1289]

13:06 If you're not taking any extra space at all, the space complexity should be O(1)

[@nikoo28]

i misspoke, you are taking the space of the HashSet which has a size (n). Hence O(n). Thanks for the correction.

[@kshitijpandey9376]

Understood the solution very well. Thank you

[@shrutisrivastava5530]

The solution was very simple to understand thankyou so much. But i had a doubt as I implemented this on leetcode, the time it took for all the test cases was: 457ms , and 9ms solutions were also available. So I have to study the more optimum approach or it is fine for technical round or interview round?

[@theexplorerayesha]

The best and simplest explanation and code I found on KZbin 🥹 thank you so much sir

[@kchemutai3483]

Great explanation, I just wanted a clarification on the time complexity, i think we left out the time complexity for sorting. What is the time complexity for sorting, otherwise the rest is O(n^2) as explained.

[@meriyemelhajoui4083]

I dont see what we should sort the array ? if we gonna loop over the loop and everytime fix and try to found a sum that s equal to 0

[@nikoo28]

Sorting the array ensures that all smaller numbers are to the left abd larger to the right. Then you look at the sum obtained…if greater than target, then you need to pick a smaller number..so just move the right pointer by 1 place instead of traversing the entire array. Saves you a lot of time.

[@architagarwal7379]

Nice explanation but there are 2 cases over here. if the array is sorted already or the array is not sorted. if the array is sorted we can go with the approach explained by nukhil but if its not sorted the better use hashmap approach which gives O[n] TC and O[N] SC

[@ZachDift-kc4nk]

does this solution actually work in leetcode? i am getting an error when i submit (not run) the code.

[@nikoo28]

yes it does, check out the complete implementation on the Github link available in video description

[@SamSafi003]

Thank you ... ❤

[@GouravKumar-r2p]

Nikhil We want 4sum leetcode solution.

[@sysybaba420]

you are using a set to arrive at a solution right? so how do you say that you are not using any extra space? or is it just constant space?

[@nikoo28]

it is constant space.

[@gireeswar18]

Perfect Video !!!

[@rishikakoul6336]

CAN ANYONE EXPLAIN ME WHY HE DID ELSEIF(SUM

[@sumitkaranjkar3819]

as he explained we need to adjust the index as per the sum ex- if sum

[@AzharKhan-e9m]

isme ek problem hai duplicate triplets ko lekr ... triplets double print horhe

[@hajarelalit]

Nice solution, I have now subscribed to your channel, very good explanation and solution. I want to clear Toptal interview, please guide me in some way if possible. Thanks !

[@harshitha5929]

Good evening sir Thank you for such a keen explanation. Sir can you do leetcode problems on python 😊

[@AteebTahir-z1i]

but how to handl eduplicates

[@nikoo28]

that is why a hashset is used

[@Jaylight977]

Bro please bring more video on trees and graph

[@nikoo28]

i am adding more and more videos every week. I am myself limited by resources and time. Hope you understand...if you have a particular topic/question in mind, let me know..and I can add it to my video list.

[@MadhavanMan]

@@nikoo28 Complete binary search problem series

[@nikoo28]

The complete playlist on graphs is now available: kzbin.info/aero/PLFdAYMIVJQHNFJQt2eWA9Sx3R5eF32WPn

[@rupeshpatil6957]

Thanks Brother

[@hoddybhaba6704]

Easy to understand!!!

[@anuragdutt36]

Bhaiya, the explanation is so good but we have to skip the duplicate triplets. So, we have to do this If (i>0 && nums[i]==nums[i-1]){ Continue; } Duplicate triplets are the question [-4,-1,-1,0,1,2] are See the [-1(1 idx),0,1] and [-1(2 idx),0,1].. Thank you.❤

[@Prm906]

to skip duplicates thats why he uses hashset

[@sandeepkashyap7239]

great great explanation

[@mikedelta658]

Thank you

[@arambh-gaur]

This is a good solution but the use of Set and then copying it back into a list is increasing the time complexity further, you fail to take that into account, on leetcode this solution takes more than 800ms which will not be good enough to clear the interview where they are expecting the optimal solution. Maybe you should also post how well your solutions perform compared to others on leetcode.

[@asr.explores]

well explained

[@user-qy2fm3pu2b]

great man

[@ShantanuSaha-vo6zh]

Notice that the solution set must not contain duplicate triplets. Your solution will return duplicate triplets. For example: [-2,0,0,2,2]

[@nikoo28]

we do handle duplicates. What output did you get with this test case?

[@omkar._.k]

Perfect

[@codeit3]

thnks

[@rgowtham9445]

good 🤩

[@VIJAYMAMORIA-c8m]

Bro, Your solution is wrong where you are assuming that HashSet will remove duplicate Lists. {1,2,3} & {3,2,1} are two different lists. They wont be considered duplicate by the HashSet as List equals method wont return equal for both. Set result = new HashSet(); result.add(Arrays.asList(1, 2, 3)); result.add(Arrays.asList(3, 2, 1)); System.out.println(result.size()); // Prints 2 NOT 1

[@nikoo28]

That is why I sort the array. :)

[@VIJAYMAMORIA-c8m]

@@nikoo28 Ok. got it. Since always the sorted List is added to the Set duplicate list addition is taken care of by the Set. But we can optimize the solution to avoid trying to add even those duplicate lists. int twoSum = A[left] + A[right]; if (twoSum == sum) { triplets.add(Arrays.asList(A[i], A[left], A[right])); /** * Only if we have found a solution for two values we can be sure we should move ahead of all their * duplicates. */ while (left < right && A[left + 1] == A[left]) { ++left; } ++left; while (left < right && A[right - 1] == A[right]) { --right; } --right; }

[@TuringTested01]

I think one more optimization you can do is this: Keeping a boolean array of "done" numbers and marking the numbers with which triplets are already made, because there could be duplicates of each number and for each of them you dont have to find the triplets because triplets would be unique, for example: if there is an array of 3000 integers all containing zero, your code would go to every zero and find the triplets using all zeros whereas the answer would just be [0,0,0]

[@gauratomar]

In this way some cases would be lost as -1, 0,1 and 2,-1, -1 are also there both use -1 and both are different trplets

[@rawatbrothers0yt968]

why are you looking like young Narendra Modi

[@vinaypratapsingh339]

if you sort the array, you will lost the indices.

[@pradeepphulse4876]

But you need to return the values. Not the indexes.

[@vamshigud151]

stock market bear bank side

[@SuriyaT3001]

This is not right .. pls check it out it gives duplicate output but in question they asked only unique subsets.. while dry run of your code pls execute in leet code itself ..

[@nikoo28]

check the code available on github in description. It does pass on leetcode.

[@ngm-oe8ow]

he is storing it in a HashSet so it won't have duplicates.

[@BharathVasudevan-s9u]

Your videos are awesome, thanks for all the details. Can we avoid having the duplicates, like adding memorization? Is that possible?

[@VIJAYMAMORIA-c8m]

You are correct. His solution is wrong. it wont remove duplicates.

[@parthbhayana6326]

Jo bhi bolo Hairfall toh bhot hogya 2 saalo me. 😂

[@nikoo28]

can't escaping aging 😅

[@joydeep_]

Sorry to say, but not the best approach.

[@nikoo28]

what would you suggest?

[@ibrahim-abdallatif]

Thanks for the clear explanation, but please note that this solution allows duplicate triplets in the result, which is not correct and won't pass leetcode submission (I tried it myself), here is the correct solution after some changes: >>> EDIT: When I tried it I was using a LinkedList instead of a HashSet as shown in the video(using HashSet won't allow duplicates indeed and hence the presented solution is correct), anyway here is the correct way to solve it with LinkedList. class Solution { public List threeSum(int[] nums) { Arrays.sort(nums); List result = new LinkedList(); for (int i = 0; i < nums.length -2; i++) { if(i == 0 || (i > 0 && nums[i] != nums[i-1])) { int left = i + 1; int right = nums.length - 1; while(left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while(left < right && nums[left+1] == nums[left]) left++; while(left < right && nums[right-1] == nums[right]) right--; left++; right--; } else if(sum < 0) { left++; } else { right--; } } } } return result; } } // TC: O(n^2), SC: O(n)

[@nikoo28]

the solution I provided on my github profile does pass leetcode.

[@satyaganesh7159]

Set uses equals and hashcode to compare elements in it, so list1.equals(list2) compares each element sequentially