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.
@@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
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
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.
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
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 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 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.
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.
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.
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)
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.
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.
am so glad that he came back and run the code!!!
nums[i] != nums[i-1] but in teh example they have two -1s, if you sort it then it is i and i-1
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
How the hell, you made it look so easy.... man I am subscribing to your course.
tough question for me , i couldn't get the solution for leetcode so i came here. helps alot, thanks man!
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
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!
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()
Your simple explanation just made it easy... but its not! You're awesome!
All these people remember the algorithm and thats it. Dont sweat it guys just memorize
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?
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
To anyone looking for C++ solution:
class Solution {
public:
vector threeSum(vector& nums) {
vector ans;
if(nums.size()
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.
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...
Do we have any other approach where we can reduce the time complexity?
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
Great video and I have always found the name of this question…interesting
Algorithm so much simpler than other peoples like it’s ridiculous how complicated they can make this problem lol
Bless your soul
Very clear and great explanation
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.
clear explanation about the usage of two pointers to solve complex problem. Keep up the good work !
god bless !!!
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.
there's no way in hell you solved this in real-time.
What if the array contains only [-2,1,1] how does the code check for the duplicate?
Great explanation, you don't sound like you want to be alive, but great explanation!
Can you please add the time complexity and space complexity explanation for each problem you solve?
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 []
that ending was perfect lmao
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
not a 3some i dream about , but super useful)
Thank you Nick. but why used LinkedList instead of ArrayList here?
great video, could you explain why you used a LinkedList as opposed to the nested ArrayList?
u can use new ArrayList(); also.
TwoSum array doesn't require array to be sorted...Why did you sort it out?
Thanks for the clear explanation. What is the time complexity of this?
O(n^2)
@@brycejunkinz O(n^2) + n
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.
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
Super easy and nice explanation. Thanks Nick
Nicely explained! Well done.
Thanks Nick by heart 💓♥️
Thank you! You made it so simple with your explanation.
Great Explanation,Thanks!
Clear explanation! Thank you!
Threesum is similar to twosum -
Nick White
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.
This does not remove the duplicates.
Keep it up. I love your videos
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.
Great solution!
Great solution brahh.
What is the time and space complexity for this?
why do we need the i==0 in if (i == 0 || nums[i - 1] != nums[i])
This is awesome, thank you!
God, this is so confusing still
why didn't you use the hash table method for 2 sum
Does anyone knows which companies ask for this question?
Only devs can get away with saying 3some in workplace
[0,0,0] it won't work
Thanks
MY BOI AT IT AGAIN
nice solution!
The real world 3 some is not even a problem.
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.
line 15 16 17 18 why do you write twice low++ high ++
In the example [-1,-1,2] isn't it duplicate
it's still O(n^2) right
Yes, but it's a decent runtime for this problem
ok, so he basically make the three numbers to be unique.
I have a question here why we used linked list instead of ArrayList
U can use both
Good Work!
ur great sir!!
Can anyone explain why a linked list was used?
I didnt understand the sorted part like why do we sort it
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]);
good explanation
the only 3sum i can afford
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)
This code doesn't work for [-1,-1,0,1]
i think your linkden url is broken here.
This does not work for [0,0,0] as an input
Why i>0? in line 7?
bro you are awesome
Like your video. Thanks
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);
}
very excellent， thanks
but you sorted the array, was it allowed?
bsuperbrain as long as it isn’t prohibited it is allowed
@@willinton06 lol
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
I got TLE following this approach in python..Don't know why
Was waiting for hashmap...never came
Why did he handle duplicates twice?
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
can you please tell me the exact real time application of 3sum problem ..
Awesome !
Good solution but not time efficient..faster than only 40% of the submissions.
How the fck is someone supposed to solve this in 45mins???? Smh
Who here for LeetCode July Challenge?
I don't get it