Interview Question: Three Sum

[@prateeksharma1047]

The initial for loop should run till len-3 to cover the case if we have exactly 3 values in array. for(int i = 0 ; i

[@ByteByByte]

Yep you're right

[@johnyeukhonwong830]

yeah for < it would be -2 [ A, B, C] len = 3, max index = 2, then i < 1, so A is the only one i will ever visit.

[@claramartinezrubio7768]

Great catch!!! @Sam you should've updated your video to show that.....at least make a note on it!

[@lei8022]

Should we change line 4 i

[@micahmyers2558]

Working in Python but the idea behind the code is all I needed. Thanks!

[@alexhong794]

yeah the for loop should be i < length - 2 cause we have 3 pointers and we have to leave 2 positions to start and end and the boundary of the loop would be equal to length - 3 since array is counted from 0, so i should less length -2 which is i < length -2. But anyway, thanks for sharing your idea, I like the analysis of those test cases, it makes ppl easy to understand your algorithm. Good job!

[@subhankarhotta7094]

In the first if statement inside the while loop, after adding to the result array, the start pointer should be incremented and the end pointer should be decremented simultaneously else the code would run to an infinite loop.

[@amartya991]

actually it's not required. Because he is using if if and else so that would increment and decrement the value of start and end depending on the conditions. Just putting it out there. I also got confused for a bit

[@wpavada3247]

Three sum is always a problem! ;)

[@saurabhvaidya4228]

Not anymore

[@readingsteiner6061]

indeed, sire!

[@tannerbarcelos6880]

saurabh vaidya legend

[@MrThepratik]

most underrated video on youtube . Nice work !

[@ByteByByte]

thanks!

[@chahalpawanpreet]

Thank you for this free educational content

[@skumakerguitar8708]

this solution is similiar with Nick White but the way you explain is better :) keep this up Byte Byte

[@karthikk5895]

Thanks Sam! This question was recently asked in my Google interview and I followed the exact same approach and clear my first two rounds until now.

[@ByteByByte]

Nice work! Congrats :)

[@ankitajain4194]

@Karthik K - Just curious. Did you tell interviewer that you have seen this problem before?

[@M.I.D.N.I.G.H.T-E.C.H.O.S]

@@ankitajain4194 what will you do in the similar situation ?

[@dengzhonghan5125]

I still think we should implement i to len - 2. For this example, the length is 6, len -3 is 3. So in your solution, i will be implemented until 3 but not equal to 3. So i will be only covered from 0 to 2. correct me if I am wrong.

[@lifutao3446]

Great job man, I was looking for video solutions to supplement my technical interview prep and I've found it here.

[@ByteByByte]

thanks!

[@roshnirajan4643]

Thank you so much for this video! I finally understood this and I am so happy. I was really confused when I saw this question and all I could think of was brute force approach. You made it so easy. Thanks a ton !

[@ByteByByte]

Love it!

[@GokulRG]

Thank you so much man!! great video.. only quality video on the entirety of KZbin.. that explains this problem very well... Subbed.. and looking forward to more great content on leetcode problems

[@ByteByByte]

Gokul Rama thank you! :)

[@neilpatel1023]

Nice. I was stumped on this problem. I tried to take the HashMap approach at first but like you said, it gets complicated. Thanks for explaining this O(n^2) solution!

[@ByteByByte]

You're welcome!

[@sipham_]

You are just downright amazing :) Thanks for doing it with heart.

[@dheerajmct]

Excellent Work !!! Continue the great work

[@Rogue71]

Very clever solution, thanks for sharing. I went first for the Map solution, and it is indeed trickier. This one is much more elegant.

[@ByteByByte]

thanks!

[@RajeshKrishnan1]

The solution @ 6:40. Thanks for the awesome explanation! Liked, subscribed.

[@ByteByByte]

Rajesh Krishnan thanks!

[@alxx736]

What about the Time Complexity when you are doing the sort ?

[@anilkurmi5966]

Amazing explanation thanks

[@johnyeukhonwong830]

This code will fail if you have the following: {-4, -1, -1, -1, 0, 1, 2, 2}. When we do the first (-1, -1, 2), we see it's a zero. But we only decrements end to avoid duplicate. start will move to up by one, but now it's seeing another -1. We can either use a hashmap to store the triple, or the while loops to do advance on duplicate to be outside of the the check.

[@vikasjain2969]

Awesome solution. Thanks for sharing this.

[@lifeofme3172]

Why do we have a another if block after checking == 0 than using a else block?

[@shishkabob50]

Been searching so long for a youtube channel like yours. Amazing work!! Sub!

[@ByteByByte]

Thank you!

[@ericsmithson8193]

Your first if statement should check for the negative case and continue if it finds it. i.e. if( i > 0 && arr[i] == arr[i - 1]) { continue }. This reduces the amount of indentation and makes it more clear that you’re trying to avoid a certain case rather than running on a certain case.

[@ByteByByte]

I'm not sure I totally agree with you from a style perspective, but I get what you're saying

[@nealpatel7696]

In your time complexity analysis, you didn't account for the while loops for when you're skipping over duplicates. What if we had all duplicates but the last element and there was no valid triplet sum? Wouldn't that make it nearly O(n^3)?

[@ankurjain6393]

Great explanation! Just one thing..the for loop should run till i

[@ByteByByte]

Ah yes, I think you're right.

[@prateekjoshi90]

Nope it works fine the only thing wrong with the code is that we need to increment and decrement start and end in case where arr[i]+arr[start]+arr[end]==0

[@ToyMachine22122]

I must be missing something... it looks to me like you’re still evaluating all possible triplets. To select the set of all possible triplets is going to be O(n^3). My solution was to sort the list, then iterate over the set of all possible pairs. For each unique pair of elements (x,y) where x and y represent the value of those elements, perform a binary search for an element whose value is (-1)*(x+y). If binary search is successful, add the triplet to our result; else continue to the next pair. To get the set of all possible pairs is O(n^2); binary searching for the value needed to bring the sum to zero is O(log(n)). Thus final running time for my solution is O(n^2*log(n)). Does your solution have me beat? Because you’re not using a binary search, I don’t see how yours could be better but maybe I’m missing something. To avoid duplicates I used a hashtable to track which triplets had already been evaluated. Since hashtables are awesome data structures with constant time for insertion and search operations, this doesn’t change the time complexity.

[@AH-xb7eb]

It's O(n^2) because for every value in nums, you're doing another linear search since it's two pointers converging.

[@oliverinspace47]

Hey that while loop runs into an infinite cycle when you find a solution because you aren't changing any variables for the check. You need some sort of change to end the while loop on top of it. Just add the same loop within the other if cases of incrementing start. .... while(start < end) { if (arr[i] + arr[start] + arr[end] == 0) { results.add(new int[] {arr[i], arr[start], arr[end]}); int currentStart = start; while (arr[start == arr[currentStart] && start < end) { start++; } } .....

[@meharkaur7326]

Same doubt ^^

[@461932570]

Brilliant explanation !

[@Dyslexic_Neuron]

Why are we only looking on the right side of the remaining array ? Couldn't there be a possibility that the elements left of the current pivot element add to the right of the pivot element and give inverse of the pivot ?

[@roshanreji3440]

Thank you for the great explanation. Although I think that in the for loop the condition should be i < arr.length - 2 ?

[@namratam1522]

No. Array indices always start from 0. So last index is length-1, 2nd last is length-2 and third last is length-3. We wanna increment i till 3rd last index.

[@MdJahid-kd2ts]

Great work!! Please keep going!! its amazing effort by you!!

[@ribhavhora9576]

Why would you want to keep incrementing start or decrementing end when you know that number does not lead to a solution? (It's not wrong to do it, it increases efficienct, but I don't see the need) Incrementing start and end should only be done when we know it is a solution, i.e., in the first if. Please correct me if I'm wrong!

[@vinay0071]

Excellent explanation. Thanks !!

[@ByteByByte]

thanks!

[@itzeltravels]

How can we modify this solution for the four Sum, where we have to find four numbers that add up to a sum S? Is it possible to have four pointers, two at the beginning of the array and two at the end and move the pointers according whether their sum is less than or greater than the sum S?

[@venkateshkadali1137]

Hi, @BytebyByte. That's a Good Explaiation. And this is not working for {-4,-1,-1,0,2,2}. This is returning the duplicated triplets. I think you should add the below code in if(arr[i] + arr[start] + a[end] == 0). start++; end--; while(start

[@rajastylez]

So clear!

[@skirtingtheedge6687]

Elegant but I don't think it returns complete results. For example given the array {-4, -2, 0, 1, 1, 2, 3, 4, 6}, your code returns 5 sets of 3. The brute force method returns 6. There are 2 sets of (-4, 1, 3) but the code will jump i++ once the first set is returned ignoring the 2nd set.

[@TM-qc5oz]

why 6 ? There are only 5 unique sets : (-4,1,6),(-4,3,4),(-2,1,4),(-2,2,3),(0,1,2)

[@shayanasgari5594]

If you sort the array, is there any point of that if statement( i==0|| arr [i]

[@ByteByByte]

That if statement would be false if arr[i] == arr[i+1]

[@shayanasgari5594]

Byte By Byte Ah. So we want to ignore those numbers that are the same?

[@ByteByByte]

Yep

[@omnilash93]

Some of the comments say that we need to start++ or end-- in the ==0 case. Is this true? Won't the else condition always take care of that as

[@varunnarayanan8720]

Well explained

[@badatpad2]

Hello, thanks for a great video, was struggling with this on leetcode, but now I understand One additional problem with the code in the video is that in the case of a success (sum all 3 numbers == 0 case), start should be incremented to the next unique value, otherwise the while loop will run forever at that point i think?

[@ByteByByte]

yep I think you're right. nice catch!

[@GG-hk5iz]

The above code is in which programming language?

[@ByteByByte]

All the solutions on my channel are in java :)

[@arjun9951]

Good video. Thanks

[@ByteByByte]

thanks!

[@umyothein7363]

pretty well explained....helped me a lot.....

[@ryangiordano3338]

Thank you, you were able to explain three sum in such a way that it finally clicked with me. Now to convince my wife.

[@nikhilurkude5880]

I guess if(arr[i]>arr[i-1]) will give array index out of bound error. Correct me if I am wrong

[@gauravdudeja]

there is || condition for that

[@vamsi54krishna]

no bcoz there is short-hand '||' before when it, means when i==0 then if expr is evaluated to TRUE w/o checking second operation right to '||'

[@GokulRG]

Also could you please provide a link to your code solution so that we can also get the textual copy

[@ByteByByte]

Gokul Rama there's already a link in the description :)

[@sididiaby5784]

So the runtime doesn't go below O(n^2)

[@farazahmed6043]

hey awesome video. Does this technique have a name? I have seen it in other problems too

[@ByteByByte]

Thanks! I have no idea if it has a name or not

[@poluribharadwajreddy3814]

Nuvvu thop anna

[@piyush12121]

Nice Job !

[@ByteByByte]

+Piyush Chaudhary Thank you!!

[@piyush12121]

+Byte By Byte I think it will fail on [0,0,0].

[@ByteByByte]

+Piyush Chaudhary I'm pretty sure it should work. In any case where the input length is three, it should test the 3 values and then add them to the list if they sum to zero and return an empty list otherwise. Let me know if I'm missing something or if you'd like a more detailed explanation

[@patrickpei9256]

Piyush is correct - your loop runs while i < arr.length - 3 meaning that if you had an array of [0, 0, 0], i would obviously start at 0 and 0 is not less than 0 thus skipping that result.

[@ByteByByte]

Yep you're totally right. Thanks for helping clear that up!

[@alexpena9927]

i got an infinite loop inside the first if statement inside the while loop. (it adds the same solution over and over again because left and right is not incrementing)

[@alexpena9927]

update: I just incremented start++ in the first if statement and everything worked

[@ugene1100]

Thank you sam for the video, great info :)

[@ByteByByte]

you're welcome!

[@pursuitofcat]

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) if n 0: break if i >= 1 and nums[i] == nums[i - 1]: continue target = -nums[i] left = i + 1 right = n - 1 while left < right: if nums[left] + nums[right] < target: left += 1 elif nums[left] + nums[right] > target: right -= 1 else: output.add((-target, nums[left], nums[right])) left += 1 right -= 1 return [list(item) for item in output] s = Solution() assert s.threeSum([-1, 0, 1, 2, -1, -4, -3, -2, 2, 3, 4, -6, 5]) == [ [-6, 1, 5], [-6, 2, 4], [-4, -1, 5], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-3, -2, 5], [-3, -1, 4], [-3, 0, 3], [-3, 1, 2], [-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1], ]

[@romanesterkin]

it should be "i

[@robbiesoho]

brilliant. thank you

[@gauravdudeja]

It will give duplicate output for [-2,0,0,2,2] -> [[-2,0,2],[-2,0,2]]. I think we can use set here.

[@ByteByByte]

That depends on whether you consider those to be duplicates or not.

[@TheEndimanche]

But this doesn't take into consideration an arrray that has all zeroes, for example [0,0,0]. It should return simply [0,0,0], but this solution would return an empty array [ ]. Great work by the way!

[@TheEndimanche]

Nvm, I think you have to make your i pointer until i < 2, NOT i

[@prashanthnaik7534]

Does this work on [0,0,0] input value?

[@bantyK]

No. You have to change the outer loop(with variable i) from i < nums.length - 3 to i < nums.lenght - 2. Then it works. I verified it in leetcode leetcode.com/submissions/detail/289991349/

[@mamtanigam7490]

I am not getting correct result for the case when input is [0,0,0], can you please explain why?

[@isreehari]

iterate arr.length - 2 instead of arr.length - 3 because if you it arr.length then it will not enter into first while loop because start < end.

[@saurabhvaidya4228]

Great video

[@ByteByByte]

thanks!

[@NitaNair]

Thank you so much

[@Israeli8103]

I think your code won't work for this {-1,0,1} since it wont get into the first for loop

[@siddharthbhagwat2957]

This code does not pass the test case when the input is [0,0,0]. Any Suggestions?

[@jason18401]

Make a base case.

[@jisunnoh2796]

The for loop should be for (int i = 0; i < arr.length - 2; i++), not 3. It will skip any 3 elements.

[@Eugene.Berezin]

Thanks, man! I wanna be like you when I grow up lol. Great explanation!

[@tsupreetsingh]

You wanna be a fraud ?

[@Eugene.Berezin]

Supreet Singh what makes you think that he’s a fraud?

[@wenchen210]

Can anyone help me to answer the space complexity of this problem? Is it O(1)? or O(n): because of new ArrayList Which one?

[@somemathkid2889]

O(n) think about this case: [-1, 0, 1]... u return [[-1, 0, 1]]

[@wulymammoth]

Luke Roche that’s incorrect. In accordance with the multi-tape Turing machine space complexity definition, we don’t count input or output “tape” (space). We only consider the maximum space allocated (variables, stack space [explicit or call stack], etc) to perform the operation. Now, if we used the results as a form of look-up then this would be O(N), but as it stands, it is O(1)

[@mathiasg5514]

You are missing a "break" in the if test that checks for == 0 (where you add to results). The program gets stuck in the outer while loop if you omit this break.

[@pradiptarakshit35]

break statement is taken care of by the else statement, it will decrement the end

[@vishwanathpatil2995]

Kindly do a video on the following problem Leetcode 706. Design HashMap

[@mohanreddy4669]

isn't the complexity O(nlogn) ?

[@aviralsaxena5153]

No, sorting is nlogn, but after sorting there is a for loop, which in worst case takes n time and inside that for loop is a while loop which in worst case is also n times. So that for loop is n^2 time. Since the sorting and n^2 nested loops are separate, the algorithm is O(n^2 + nlogn) time. You take the bigger of the two so it becomes O(n^2).

[@dattu06]

There should be a break statement in this if loop. Else it will be running in infinite loop. if ((arr[i] + arr[start] + arr[end]) == 0) { results.add(new int[] {arr[i], arr[start], arr[end]}); break; }

[@aravindsrivatsa7709]

Not a break statement because, if you break, you will miss out on those solutions which can be formed out of the same value for current index of i, and different values of start and end. Instead, you should keep incrementing start and decrementing end based on the same logic as below, so as to keep avoiding duplicates : int currentStart = start; while (nums[currentStart] == nums[start] && start < end) start++; int currentEnd = end; while(nums[currentEnd] == nums[end] && start < end) end--;

[@vishalvyas4221]

Please let me know if you are seeing any issue in logic: a+b+c = 0, so, a+b =- c or a+c = -b or b+c = -a or ========= I used TreeSet to avoid duplicate combination and final list in sorted order.. Also, in set not repeating same number again.. {-1, 2, -1} not allowed as -1 repeating twice.. Please share if solution is not OK to accept...(just wondering).. ................................................................................... int A[] = {-1, -3, -2, -1, -4, -5, 1, 3, 1, 2, 3, 4, 5, 7, 8}; Set resultList = new TreeSet(); List myList = new ArrayList(); for(int i=0; i

[@siddhishah__cse5796]

can anyone tell me the real life example of this 3sum problem ..

[@yuezhongqiu8653]

Mark Cuban teaching me how to code

[@sagarchalla3089]

Great explanation, everything so detail and precise. Nice Job! I have one question though, the algorithm seems to be inconsistent when the input is [0, 0, 0]. This is probably one edge case that needs to be considered here.

[@anandpurushottam4435]

code is not fully correct

[@trevorbekun7039]

Dont lie you laughed at the beginning.

[@shreyaslengade8830]

:D

[@dibyajyoti_ghosal]

DO you even know what you've written? try with this input! [3,0,-2,-1,1,2]

[@cristiankublaigomezlopez2303]

Just tried it. Result [[3,-2,-1],[0,-2,2],[0,-1,1]] Have a good day! 😁

[@saptarshimitra1267]

Great

[@kuldeepnarayanminj]

clicked at the speed of bullet, just after seing title

[@numberjuan297]

Three Sum (;

[@nikulpatel2319]

Man !! At least run your program once to make sure it is correct.. lots of errors in it....... :(

[@DrDangers]

Q U A L I T Y

[@DrDangers]

by the way searching "three sum" in youtube gives some fun results

[@ByteByByte]

Thanks!

[@ByteByByte]

and somehow I'm not surprised...

[@josephluce7281]

In a real interview, you would lose points for not separating responsibilities with a second function. So many other problems with this solution. This is not good.

[@bigray712]

sorry but you talk way too much. it shouldn't take 27min to explain this.

[@ByteByByte]

did you watch the video?