Interview Question: Three Sum
Vložit
- čas přidán 28. 08. 2024
- Coding interview question from www.byte-by-byt...
In this video, I show how to solve the three sum problem.
Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.
Stuck on Dynamic Programming? Check out our free ebook: www.dynamicprogrammingbook.com
50 Practice Questions: www.byte-by-by...
You can also find me on
Twitter: / bytebybyteblog
Facebook: / bytebybyteblog
Email: sam@byte-by-byte.com
this solution is similiar with Nick White but the way you explain is better :) keep this up Byte Byte
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!
Working in Python but the idea behind the code is all I needed. Thanks!
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
Yep you're right
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.
Great catch!!! @Sam you should've updated your video to show that.....at least make a note on it!
Three sum is always a problem! ;)
Not anymore
indeed, sire!
saurabh vaidya legend
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.
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
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.
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.
Nice work! Congrats :)
@Karthik K - Just curious. Did you tell interviewer that you have seen this problem before?
@@ankitajain4194 what will you do in the similar situation ?
Should we change line 4 i
most underrated video on youtube . Nice work !
thanks!
Thank you for this free educational content
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 !
Love it!
Great job man, I was looking for video solutions to supplement my technical interview prep and I've found it here.
thanks!
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.
Great explanation!
Just one thing..the for loop should run till i
Ah yes, I think you're right.
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
Thank you so much man!! great video.. only quality video on the entirety of CZcams.. that explains this problem very well... Subbed.. and looking forward to more great content on leetcode problems
Gokul Rama thank you! :)
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.
It's O(n^2) because for every value in nums, you're doing another linear search since it's two pointers converging.
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!
You're welcome!
Very clever solution, thanks for sharing. I went first for the Map solution, and it is indeed trickier. This one is much more elegant.
thanks!
The solution @ 6:40. Thanks for the awesome explanation! Liked, subscribed.
Rajesh Krishnan thanks!
You are just downright amazing :) Thanks for doing it with heart.
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.
I'm not sure I totally agree with you from a style perspective, but I get what you're saying
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.
why 6 ? There are only 5 unique sets : (-4,1,6),(-4,3,4),(-2,1,4),(-2,2,3),(0,1,2)
Thank you, you were able to explain three sum in such a way that it finally clicked with me. Now to convince my wife.
Amazing explanation thanks
What about the Time Complexity when you are doing the sort ?
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++;
}
}
.....
Same doubt ^^
Why do we have a another if block after checking == 0 than using a else block?
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!
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)?
Thank you for the great explanation. Although I think that in the for loop the condition should be i < arr.length - 2 ?
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.
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
Been searching so long for a youtube channel like yours. Amazing work!! Sub!
Thank you!
So clear!
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 ?
Nuvvu thop anna
Excellent Work !!! Continue the great work
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],
]
Awesome solution. Thanks for sharing this.
Brilliant explanation !
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!
Nvm, I think you have to make your i pointer until i < 2, NOT i
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?
yep I think you're right. nice catch!
Great work!! Please keep going!! its amazing effort by you!!
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?
Excellent explanation. Thanks !!
thanks!
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
it should be "i
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)
update: I just incremented start++ in the first if statement and everything worked
pretty well explained....helped me a lot.....
I guess if(arr[i]>arr[i-1]) will give array index out of bound error. Correct me if I am wrong
there is || condition for that
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 '||'
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
I think your code won't work for this {-1,0,1} since it wont get into the first for loop
Good video. Thanks
thanks!
If you sort the array, is there any point of that if statement( i==0|| arr [i]
That if statement would be false if arr[i] == arr[i+1]
Byte By Byte Ah. So we want to ignore those numbers that are the same?
Yep
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.
break statement is taken care of by the else statement, it will decrement the end
Well explained
Nice Job !
+Piyush Chaudhary Thank you!!
+Byte By Byte I think it will fail on [0,0,0].
+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
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.
Yep you're totally right. Thanks for helping clear that up!
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.
hey awesome video. Does this technique have a name? I have seen it in other problems too
Thanks! I have no idea if it has a name or not
Mark Cuban teaching me how to code
The above code is in which programming language?
All the solutions on my channel are in java :)
So the runtime doesn't go below O(n^2)
Thank you sam for the video, great info :)
you're welcome!
It will give duplicate output for [-2,0,0,2,2] -> [[-2,0,2],[-2,0,2]]. I think we can use set here.
That depends on whether you consider those to be duplicates or not.
Also could you please provide a link to your code solution so that we can also get the textual copy
Gokul Rama there's already a link in the description :)
Thanks, man! I wanna be like you when I grow up lol. Great explanation!
You wanna be a fraud ?
Supreet Singh what makes you think that he’s a fraud?
I am not getting correct result for the case when input is [0,0,0], can you please explain why?
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.
brilliant. thank you
can anyone tell me the real life example of this 3sum problem ..
Thank you so much
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;
}
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--;
This code does not pass the test case when the input is [0,0,0]. Any Suggestions?
Make a base case.
The for loop should be for (int i = 0; i < arr.length - 2; i++), not 3. It will skip any 3 elements.
Great video
thanks!
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?
O(n) think about this case: [-1, 0, 1]... u return [[-1, 0, 1]]
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)
code is not fully correct
Does this work on [0,0,0] input value?
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/
Kindly do a video on the following problem Leetcode 706. Design HashMap
Dont lie you laughed at the beginning.
:D
isn't the complexity O(nlogn) ?
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).
Great
clicked at the speed of bullet, just after seing title
DO you even know what you've written? try with this input!
[3,0,-2,-1,1,2]
Just tried it. Result
[[3,-2,-1],[0,-2,2],[0,-1,1]]
Have a good day! 😁
Three Sum (;
Man !! At least run your program once to make sure it is correct.. lots of errors in it....... :(
Q U A L I T Y
by the way searching "three sum" in youtube gives some fun results
Thanks!
and somehow I'm not surprised...
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.
sorry but you talk way too much. it shouldn't take 27min to explain this.
did you watch the video?