LeetCode 3Sum Solution Explained - Java
Вставка
- Опубліковано 11 жов 2024
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.d...
AlgoCademy - algocademy.com...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/...
Follow Me on X/Twitter - x.com/nickwhit...
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nick....
Become A Member - / @nickwhite
#coding #programming #softwareengineering
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.
nums[i] != nums[i-1] but in teh example they have two -1s, if you sort it then it is i and i-1
am so glad that he came back and run the code!!!
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
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?
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!
Do we have any other approach where we can reduce the time complexity?
Can you please add the time complexity and space complexity explanation for each problem you solve?
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
What if the array contains only [-2,1,1] how does the code check for the duplicate?
tough question for me , i couldn't get the solution for leetcode so i came here. helps alot, thanks man!
How the hell, you made it look so easy.... man I am subscribing to your course.
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
Your simple explanation just made it easy... but its not! You're awesome!
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...
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
All these people remember the algorithm and thats it. Dont sweat it guys just memorize
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.
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.
that ending was perfect lmao
This does not remove the duplicates.
great video, could you explain why you used a LinkedList as opposed to the nested ArrayList?
u can use new ArrayList(); also.
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 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.
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.
not a 3some i dream about , but super useful)
Thank you Nick. but why used LinkedList instead of ArrayList here?
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 []
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
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
TwoSum array doesn't require array to be sorted...Why did you sort it out?
Algorithm so much simpler than other peoples like it’s ridiculous how complicated they can make this problem lol
To anyone looking for C++ solution:
class Solution {
public:
vector threeSum(vector& nums) {
vector ans;
if(nums.size()
why do we need the i==0 in if (i == 0 || nums[i - 1] != nums[i])
clear explanation about the usage of two pointers to solve complex problem. Keep up the good work !
god bless !!!
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.
Great video and I have always found the name of this question…interesting
In the example [-1,-1,2] isn't it duplicate
why didn't you use the hash table method for 2 sum
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.
Great explanation, you don't sound like you want to be alive, but great explanation!
Bless your soul
What is the time and space complexity for this?
Thanks for the clear explanation. What is the time complexity of this?
O(n^2)
@@brycejunkinz O(n^2) + n
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.
I have a question here why we used linked list instead of ArrayList
U can use both
line 15 16 17 18 why do you write twice low++ high ++
there's no way in hell you solved this in real-time.
Very clear and great explanation
Threesum is similar to twosum -
Nick White
This code doesn't work for [-1,-1,0,1]
This does not work for [0,0,0] as an input
God, this is so confusing still
it's still O(n^2) right
Yes, but it's a decent runtime for this problem
[0,0,0] it won't work
I didnt understand the sorted part like why do we sort it
Thank you! You made it so simple with your explanation.
Super easy and nice explanation. Thanks Nick
Does anyone knows which companies ask for this question?
Can anyone explain why a linked list was used?
Only devs can get away with saying 3some in workplace
Nicely explained! Well done.
Why did he handle duplicates twice?
Thanks Nick by heart 💓♥️
The real world 3 some is not even a problem.
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)
Why i>0? in line 7?
MY BOI AT IT AGAIN
Keep it up. I love your videos
ok, so he basically make the three numbers to be unique.
Clear explanation! Thank you!
Great Explanation,Thanks!
I got TLE following this approach in python..Don't know why
i think your linkden url is broken here.
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
the only 3sum i can afford
can you please tell me the exact real time application of 3sum problem ..
Great solution brahh.
but you sorted the array, was it allowed?
bsuperbrain as long as it isn’t prohibited it is allowed
@@willinton06 lol
Great solution!
I think I'm starting to have a crush on you haha
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
This is awesome, thank you!
nice solution!
I don't get it
Thanks
Was waiting for hashmap...never came
Good Work!
Anyone getting output as [[1,-1,2],[1,0,1]] for input
[-1,0,1,2,-1,-4]?
No. This program is flawed
ur great sir!!
good explanation
Good solution but not time efficient..faster than only 40% of the submissions.
bro you are awesome
very excellent， thanks
Succinctly explained Nick :)
Like your video. Thanks
Awesome !