You can use a Set (HashSet) instead of a List to reduce the amount of edge cases you need to think about or amount of checks you need to do. A fair amount of your code just checking whether to skip duplicates and other edge cases, and these will be hard to remember in an interview setting. One thing I've noticed is if the result requires deduped anything, it's just easier to throw things at the Set and let the data structure do the work for you, then convert to a List on return. Otherwise, great explanation, good work!
You are a freaking genius. I'd been at this for hours trying to get this duplicate thing down and your comment ended my misery in three minutes. Thank you kind sir.
@@tommyypoon Store [-1, -1, 2] as a key and then return all the keys in array form at the end. The hash prevents you from having duplicate [-1, -1, 2] in your return set as the second one will simply overwrite the first in the hash.
@@tommyypoon One of the big tricks with this problem is figuring out what to do with duplicate answers. You can definitely work around some of these cases by taking advantage of the sorted properties of the array. But these checks can get complicated and might be error prone. So the trick is to use a data structure that does it all for you. In this case, the list of integers is a key, and any writes to the set either adds a new key or update an existing one.
Actually it works. when num[i] is the first -1, it gets -1 and 2 as low and high. When goes to the next iteration of for loop, It skips the second -1 as num[i], as it supposed to avoid duplicate.
@@AniketSomwanshi-ll7mz Duplicate meaning : if you have -1 as the leading number (num[i]) of the triplet , then don't use it as leading number again if num[i+1]= -1 too. otherwise, you'll have duplicate. Duplicate does not mean avoid repeating numbers in the triplet itself, so you will not exclude in your result. If you are still confused, try stepping into his code with real input. For instance, WHEN array is {-1, -1, -1, -1}, and target sum is -3, THEN result should contain only 1 triplet , instead of 2.
Yes, you can use the hashmap also to solve two sum, and when we are doing that we need not to sort them, but in 3sum , sorting is necessary that's why instead of using hashmap we can use two pointer technique which will save space anyways you can also solve 3sum with hashmap
@@MahirHasancse21 Time complexity won't change if we use a hashmap in this case since the tc of a hashmap lookup is amortized O(1), from my understanding.
I get a random runtime error at a test case during submission. "[-7,-4,-6,6,4,-6,-9,-10,-7,5,3,-1,-5,8,-1,-2,-8,-1,5,-3,-5,4,2,-5,-4,4,7]" is the last input. "Heap buffer overflow". Not sure where I'm going out of bounds in this case, just getting the registers in the error message. Edit: Followed the call stack plugging it into visual studio, found the problem. Ran out of room for my answer vector. Updated the program to resize more appropriately. :) Unfortunately run time doesn't seem great. Not sure if the vector resizing is slowing it down.
Thanks for solution. I have a question. Like this question, in some question, I have an error called Time Limit Exceeded. Actually code is true, but code can be crowded. What could you recommend for this issue?
Took me a while to understand. [i] != [i-1] because if same num[i] is found then results would also be the same. We want to avoid same results. Same for while(low
sir thank you so much for people like me who can't afford courses you are great help sir did you upload all the problems you have ever solved on youtube or there are some which you haven't uploaded here
For some reason this code doesn't work on leetcode, I hope I haven't made any mistakes. But if you put low and high increments before whiles and comment out the second while(duplicate search) the code passes tests.
True True, this is what he wrote(just for reference, if required) class Solution { public List threeSum(int[] nums) { List l1 = new ArrayList(); Arrays.sort(nums); if(nums.length==0 || nums.length==1 || nums ==null) return l1; for(int i=0; i< nums.length-2; i++){ if(i==0 || (i> 0 && nums[i]!=nums[i-1])){ int low = i+1, high = nums.length-1, sum = 0-nums[i]; while(low
@@vikramreddy7586 Technically, the need to sort arises in this question due to the two pointer method he uses for two sum, which you cannot use without a sorted array. An added advantage to sorting is that it takes care of duplicates.
@@abhipsamohapatra852 since the brute force approach for this problem is n^3, you can afford to do two sum with sorting and the two pointers because that will give you an overall runtime of n^2. If you were to use the hashmap approach, you would have the same running time but need to allocate additional space
@@jaredtewodros I am using two for loops and still getting time out error. It should be O(n^2) right? ans = [] for i in range(len(nums)): for j in range(i+1, len(nums)): k = -(nums[i] + nums[j]) if k in nums[j+1:]: temp_arr = [nums[i], nums[j], k] temp_arr.sort() if temp_arr not in ans: ans.append(temp_arr) return ans
doesn't this solution skip over [-1, -1, 2], through your solution, if you sort it first you get [-1, 0, 1] then you skip the next -1 you see and never get the other solution, right?
@@leomonz I rewatched it and realized you actually find [-1,-1,2] first before you find [-1,0,1] Sort the array [-4, -1, -1, 0, 1, 2] i = 0 low = index 1 high = index 5 sum = 0 - (-4) = 4 // go through while low < high loop and didn’t find a sum = 4 i = 1 low = index 2 high = index 5 sum = 0 - (-1) = 1 // while low < high -1 + 2 == 1 which equals sum, if condition satisfied output.add([-1, -1, 2]) is index 2 == index 3, no is index 5 == index 4, no low = index 3 high = index 4 // still inside while (low < high) loop 0 + 1 == 1 which equals sum, if condition satisfied output.add([-1, 0, 1]);
We are looping through the entirety of the array - 2 which is a linear operation. In each iteration we are performing a two sum, two pointer algorithm which is also a linear operation. All of this is dependent on the size of the inputted array n. Thus, time complexity is O(n^2)
Forgot we sorted this array as well in the beginning of the function so O(nlogn + n^2) to be exact, but we drop the lowest multiplier so it would still be O(n^2)
this is a good explanation of the solution, but a poor representation on how to reason through the problem and come to the solution that was explained. Giving the fish but not teaching how to catch it typa-thing
I don't understand how this gets all possible solutions. How is it necessarily true that nums[low] + nums[high] would equal the sum. What if it was nums[low] + nums[high-1] = sum. We would never get that value then because you increment low and high at the same time.
He first sorted the array, then going from start and going from end. If sum is > then decrement end counter else increment start counter. The key here is that he sorted the array first.
I am getting timeout for the below code. Looks to me I am doing similar to what is shown in video. My solution is to use three pointer and remove duplicate using set. How can I optimize it further ? Any idea/hint? public List threeSum(int[] nums) { Set set = new HashSet(); if (nums == null) { return new ArrayList(set); } int arrLen = nums.length; if (arrLen < 3) { return new ArrayList(set); } Arrays.sort(nums); int i = 0; int j = 1; int k = arrLen - 1; int sum = 0; while (i < arrLen && j < arrLen && k < arrLen) { sum = nums[i] + nums[j] + nums[k]; if (sum == 0) { set.add(Arrays.asList(nums[i], nums[j], nums[k])); } if (k == arrLen - 1 && j == arrLen - 2) { i++; j = i + 1; if (j == k) { break; } continue; } if (k > j) { k--; } while (k == j) { k = arrLen - 1; j++; } } return new ArrayList(set); }
I love how his submit history is all red
relatable
Me too, that was very-very relatable.
Lo is like mine
if your are using c++
for(...;i
Can you please explain why this happens? For other programs, I can use for(int = 0; i>nums.size();i++){} and it works.
am so glad that he came back and run the code!!!
You can use a Set (HashSet) instead of a List to reduce the amount of edge cases you need to think about or amount of checks you need to do. A fair amount of your code just checking whether to skip duplicates and other edge cases, and these will be hard to remember in an interview setting. One thing I've noticed is if the result requires deduped anything, it's just easier to throw things at the Set and let the data structure do the work for you, then convert to a List on return. Otherwise, great explanation, good work!
You are a freaking genius. I'd been at this for hours trying to get this duplicate thing down and your comment ended my misery in three minutes. Thank you kind sir.
How would a hashset allow you to have the case [-1, -1, 2] like in the example?
@@tommyypoon Store [-1, -1, 2] as a key and then return all the keys in array form at the end. The hash prevents you from having duplicate [-1, -1, 2] in your return set as the second one will simply overwrite the first in the hash.
@@mason430 ahh i see, so you have a hashset which contains a list of integers as the keys?
@@tommyypoon One of the big tricks with this problem is figuring out what to do with duplicate answers. You can definitely work around some of these cases by taking advantage of the sorted properties of the array. But these checks can get complicated and might be error prone. So the trick is to use a data structure that does it all for you. In this case, the list of integers is a key, and any writes to the set either adds a new key or update an existing one.
nums[i] != nums[i-1] but in teh example they have two -1s, if you sort it then it is i and i-1
How the hell, you made it look so easy.... man I am subscribing to your course.
Do we have any other approach where we can reduce the time complexity?
This method doesn't gives the triplet [-1,-1,2] because it skipped -1.
yeah I was wondering about that..
Actually it works. when num[i] is the first -1, it gets -1 and 2 as low and high. When goes to the next iteration of for loop, It skips the second -1 as num[i], as it supposed to avoid duplicate.
@@yulinglang what if the correct triplet is -1,-1,-1 ? I am actually confused over why we'd just discard duplicate in this case!!
@@AniketSomwanshi-ll7mz Duplicate meaning : if you have -1 as the leading number (num[i]) of the triplet , then don't use it as leading number again if num[i+1]= -1 too. otherwise, you'll have duplicate. Duplicate does not mean avoid repeating numbers in the triplet itself, so you will not exclude in your result. If you are still confused, try stepping into his code with real input. For instance, WHEN array is {-1, -1, -1, -1}, and target sum is -3, THEN result should contain only 1 triplet , instead of 2.
@@yulinglang gotcha!! Thanks a lot!
Sir how can it be solved using hashmap as in two sum problem where we can consider the target in two sum to be negative of nums[i] ?
Yes, you can use the hashmap also to solve two sum,
and when we are doing that
we need not to sort them,
but in 3sum , sorting is necessary
that's why instead of using hashmap we can use two pointer technique
which will save space
anyways you can also solve 3sum with hashmap
@@adhishmalviya2408 Can the time complexity is N(logn) because of hashmap?
@@MahirHasancse21 Time complexity won't change if we use a hashmap in this case since the tc of a hashmap lookup is amortized O(1), from my understanding.
@@Vidur11 Thank you very much
@@adhishmalviya2408 hey can u please explain why sorting is necessary in 3 sum?
tough question for me , i couldn't get the solution for leetcode so i came here. helps alot, thanks man!
What if the array contains only [-2,1,1] how does the code check for the duplicate?
I get a random runtime error at a test case during submission. "[-7,-4,-6,6,4,-6,-9,-10,-7,5,3,-1,-5,8,-1,-2,-8,-1,5,-3,-5,4,2,-5,-4,4,7]" is the last input. "Heap buffer overflow". Not sure where I'm going out of bounds in this case, just getting the registers in the error message.
Edit: Followed the call stack plugging it into visual studio, found the problem. Ran out of room for my answer vector. Updated the program to resize more appropriately. :) Unfortunately run time doesn't seem great. Not sure if the vector resizing is slowing it down.
Thanks for solution. I have a question. Like this question, in some question, I have an error called Time Limit Exceeded. Actually code is true, but code can be crowded. What could you recommend for this issue?
This is happening because some loop is going infinite and never stops...
Can anyone explain the skip duplicate part?
basically the target would be same in case of duplicates & this way you can reduce a redundant iteration
Took me a while to understand.
[i] != [i-1] because if same num[i] is found then results would also be the same. We want to avoid same results.
Same for
while(low
Over all love your videos than others. For some reason, I can't look at solutions from other youtubers. Thank you!
Thank you so much! I've been stuck in this line for a while. Thanks to your explanation now I understand. :D
Your simple explanation just made it easy... but its not! You're awesome!
why do we need the i==0 in if (i == 0 || nums[i - 1] != nums[i])
Will the solution work for array given 0,0,0,0,0,0 and sum required is 0 ? I mean there should be one solution as 0,0,0 right ?
Should return []
Thank you Nick. but why used LinkedList instead of ArrayList here?
This does not remove the duplicates.
sir thank you so much for people like me who can't afford courses you are great help sir did you upload all the problems you have ever solved on youtube or there are some which you haven't uploaded here
What is the time and space complexity for this?
For some reason this code doesn't work on leetcode, I hope I haven't made any mistakes. But if you put low and high increments before whiles and comment out the second while(duplicate search) the code passes tests.
True True,
this is what he wrote(just for reference, if required)
class Solution {
public List threeSum(int[] nums) {
List l1 = new ArrayList();
Arrays.sort(nums);
if(nums.length==0 || nums.length==1 || nums ==null) return l1;
for(int i=0; i< nums.length-2; i++){
if(i==0 || (i> 0 && nums[i]!=nums[i-1])){
int low = i+1, high = nums.length-1, sum = 0-nums[i];
while(low
This has to be able to do without sorting right?
Keya Kinan not necessarily. If you don’t sort then tracking duplicates will be very tricky
@@vikramreddy7586 Technically, the need to sort arises in this question due to the two pointer method he uses for two sum, which you cannot use without a sorted array. An added advantage to sorting is that it takes care of duplicates.
@@vikramreddy7586 late to the party but the duplicates can be skipped with a hashset to skip the already seen elements.
Damn dude you make it look so easy. Thanks for all the help!
irl the way this guy presents the direct answer and explanation is not how your train of taught would go.
Sorting: O(nlogn)
Two loops: O(n^2)
Duplicate check: O(n^2)
Total: O(n^2) + O(nlogn)
Ikr but is this an optimal soln ?
It kinda looks like it cause brute Force soln would yield in O(n^3)
why didnt he use hashmap like in case of two sum
@@abhipsamohapatra852 since the brute force approach for this problem is n^3, you can afford to do two sum with sorting and the two pointers because that will give you an overall runtime of n^2. If you were to use the hashmap approach, you would have the same running time but need to allocate additional space
@@jaredtewodros I am using two for loops and still getting time out error. It should be O(n^2) right?
ans = []
for i in range(len(nums)):
for j in range(i+1, len(nums)):
k = -(nums[i] + nums[j])
if k in nums[j+1:]:
temp_arr = [nums[i], nums[j], k]
temp_arr.sort()
if temp_arr not in ans:
ans.append(temp_arr)
return ans
All these people remember the algorithm and thats it. Dont sweat it guys just memorize
in the case we found our answer and skip all duplicated number why move both low and high?
i've figured it out! sry for stupid question lol.
it's still O(n^2) right
Yes, but it's a decent runtime for this problem
Does anyone knows which companies ask for this question?
Bless your soul
why didn't you use the hash table method for 2 sum
Can anyone explain why a linked list was used?
doesn't this solution skip over [-1, -1, 2], through your solution, if you sort it first you get [-1, 0, 1] then you skip the next -1 you see and never get the other solution, right?
exactly my question> did you get the solution?
Andrew Tran you skip -1 in the inner while (low < high) loop, once you break out of that loop, your next nums[i] becomes -1
I also dont know how that works. Even Tommy Poon explained it and I am still confused
@@leomonz I rewatched it and realized you actually find [-1,-1,2] first before you find [-1,0,1]
Sort the array
[-4, -1, -1, 0, 1, 2]
i = 0
low = index 1
high = index 5
sum = 0 - (-4) = 4
// go through while low < high loop and didn’t find a sum = 4
i = 1
low = index 2
high = index 5
sum = 0 - (-1) = 1
// while low < high
-1 + 2 == 1 which equals sum, if condition satisfied
output.add([-1, -1, 2])
is index 2 == index 3, no
is index 5 == index 4, no
low = index 3
high = index 4
// still inside while (low < high) loop
0 + 1 == 1 which equals sum, if condition satisfied
output.add([-1, 0, 1]);
This program does not pass for [-1,0,1,2,-1,-4]. The Expected output is
[[-1,-1,2],[-1,0,1]]
Yeah, he is skipping -1 value (in the i loop) for this particular test case.
can somebody explain the time complexity for this problem?
We are looping through the entirety of the array - 2 which is a linear operation. In each iteration we are performing a two sum, two pointer algorithm which is also a linear operation. All of this is dependent on the size of the inputted array n. Thus, time complexity is O(n^2)
Forgot we sorted this array as well in the beginning of the function so O(nlogn + n^2) to be exact, but we drop the lowest multiplier so it would still be O(n^2)
TwoSum array doesn't require array to be sorted...Why did you sort it out?
I think for duplicacy handling (so we compare nth element with it's duplicate (potentially) (n+1)th
I didnt understand the sorted part like why do we sort it
sir why for "nums.length-2" their in for loop i.
Because you would need at least 2 index space for the low and high pointer
@@stanley6182000 Understood Thanks for your reply
Why i>0? in line 7?
this is a good explanation of the solution, but a poor representation on how to reason through the problem and come to the solution that was explained. Giving the fish but not teaching how to catch it typa-thing
In the example [-1,-1,2] isn't it duplicate
Very clear and great explanation
I have a question here why we used linked list instead of ArrayList
U can use both
clear explanation about the usage of two pointers to solve complex problem. Keep up the good work !
god bless !!!
using dictionary we do not need to check for all the edge cases.
def threeSum(self, nums):
collection={}
nums = sorted(nums)
for index in range(len(nums)-2):
low=index + 1
high = len(nums)-1
target = 0 - nums[index]
while low < high:
if nums[low] + nums[high] == target:
temp = (nums[index],nums[low],nums[high])
if temp not in collection:
collection[temp] = list(temp)
low+=1
high-=1
elif nums[low] + nums[high] > target:
high -= 1
else:
low += 1
return collection.values()
there's no way in hell you solved this in real-time.
I don't understand how this gets all possible solutions. How is it necessarily true that nums[low] + nums[high] would equal the sum. What if it was nums[low] + nums[high-1] = sum. We would never get that value then because you increment low and high at the same time.
He first sorted the array, then going from start and going from end. If sum is > then decrement end counter else increment start counter. The key here is that he sorted the array first.
great video, could you explain why you used a LinkedList as opposed to the nested ArrayList?
u can use new ArrayList(); also.
This does not work for [0,0,0] as an input
Great video and I have always found the name of this question…interesting
Can you please add the time complexity and space complexity explanation for each problem you solve?
but you sorted the array, was it allowed?
bsuperbrain as long as it isn’t prohibited it is allowed
@@willinton06 lol
Algorithm so much simpler than other peoples like it’s ridiculous how complicated they can make this problem lol
not a 3some i dream about , but super useful)
i think your linkden url is broken here.
all cases don't run. by this logic if array have 0,0,0 as inputs, it returns empty list
It still runs! Dry run his code.
To anyone looking for C++ solution:
class Solution {
public:
vector threeSum(vector& nums) {
vector ans;
if(nums.size()
Nicely explained! Well done.
Keep it up. I love your videos
Thanks Nick by heart 💓♥️
Great explanation, you don't sound like you want to be alive, but great explanation!
that ending was perfect lmao
can you please tell me the exact real time application of 3sum problem ..
I am getting timeout for the below code. Looks to me I am doing similar to what is shown in video. My solution is to use three pointer and remove duplicate using set. How can I optimize it further ? Any idea/hint?
public List threeSum(int[] nums) {
Set set = new HashSet();
if (nums == null) {
return new ArrayList(set);
}
int arrLen = nums.length;
if (arrLen < 3) {
return new ArrayList(set);
}
Arrays.sort(nums);
int i = 0;
int j = 1;
int k = arrLen - 1;
int sum = 0;
while (i < arrLen && j < arrLen && k < arrLen) {
sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
set.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
if (k == arrLen - 1 && j == arrLen - 2) {
i++;
j = i + 1;
if (j == k) {
break;
}
continue;
}
if (k > j) {
k--;
}
while (k == j) {
k = arrLen - 1;
j++;
}
}
return new ArrayList(set);
}
Clear explanation! Thank you!
Thanks for the clear explanation. What is the time complexity of this?
O(n^2)
@@brycejunkinz O(n^2) + n
MY BOI AT IT AGAIN
Why did he handle duplicates twice?
Thank you! You made it so simple with your explanation.
Super easy and nice explanation. Thanks Nick
Great Explanation,Thanks!
This code doesn't work for [-1,-1,0,1]
This is awesome, thank you!
line 15 16 17 18 why do you write twice low++ high ++
Good Work!
nice solution!
ur great sir!!
Great solution!
Great solution brahh.
I don't get it
Only devs can get away with saying 3some in workplace
ok, so he basically make the three numbers to be unique.
I got TLE following this approach in python..Don't know why
[0,0,0] it won't work
Anyone getting output as [[1,-1,2],[1,0,1]] for input
[-1,0,1,2,-1,-4]?
No. This program is flawed
Threesum is similar to twosum -
Nick White
God, this is so confusing still
very excellent， thanks
good explanation
the only 3sum i can afford
you're awesome ..Subscribed 👍 please upload more hard ones thanks
thank you bro I’ll be uploading a lot more soon
@@NickWhite you are great bro.please upload hard one more as well as medium also
The real world 3 some is not even a problem.
Succinctly explained Nick :)
bro you are awesome
Thanks
Awesome !
Like your video. Thanks
Was waiting for hashmap...never came
I think I'm starting to have a crush on you haha