3 Sum (LeetCode 15) | Full solution with examples and visuals | Interview Essential
Vložit
- čas přidán 2. 07. 2024
- To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
Actual Problem: leetcode.com/problems/3sum/
Chapters:
00:00 - Intro
00:39 - Problem Statement and Description
02:45 - Brute Force Approach
04:21 - Similarity to Two Sum
05:45 - Building an efficient solution
10:28 - Dry-run of Code
13:17 - Final Thoughts
📚 Links to topics I talk about in the video:
Two Sum: • Two Sum (LeetCode #1) ...
Sorting Techniques: • Sorting Techniques
Brute Force Paradigm: • Brute Force algorithms...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview
Simple ,yet optimized , thanks Nikhil!
You have just gained a subscriber. Out of all videos, this is so far the most comprehensible explanation. Thank you kind sir!!
Welcome aboard! Your feedback and love is much appreciated. Keeps me motivated :D
did this code work when you submitted it on leetcode?
@@ZachDift-kc4nk I can’t remember honestly it was a long time ago
Crystal Clear Explanation Sir
great explanation, congratulations on putting in this effort!!!
Glad you enjoyed it!
very nice explanation, before that i went through couple of video to understand properly but this time I understood . Thanks.
glad I could help
Best approach.
Very Excellent solution, was stuck in this prob for hrs
glad I could help
thank you bhaiya , i was stuck in this since yesterday
If you sort the array the complexity becomes O(nLog(n)) in the 2 sum part and you said the complexity becomes o(n), but for the 3sum sorting is okay because you are reducing it to o(n^2). The explanation was quite good and understandable thanks.
It's not like you sort an array n times in sum2, however. You sort an array once, then you iterate through it in O(n) time. You could say it's O(n + log(n)), but it's still linear time, so we simplify it to O(n).
With the inbuilt sorting or any sorting algorithm it would take O(nlog(n)) not O(log(n)) time. so O(nlog(n)+n)) simplifies to O(nlog(n)). so it's not linear time. it would take linear time if you use hashing.
True, my bad.@@ngm-oe8ow
@@peasantfaye5403 you can only solve 2 sum in O(n) with a hashmap. If you do the 2 pointer solution you will get a O(1) space complexity, but O(n*log(n)) time complexity.
why nlogn time complexity in 2sum using 2 pointer
@@bobaGogo
Too good , Thank you for sharing your knowledge
glad i could help you!!
You explain very well 👏
Great work Nikhil
Perfect Video !!!
your explanation is awesome thank you brother i was not able to solve this question before your video Now i solved.
You are most welcome
dil se pyaar aapko sir
Damn, this video made the problem super easy
Easy to understand!!!
Amazing explanation 🔥
Thank you 🙌 😄
great
great explanation
Thank you ... ❤
At 5:30 how the time complexity is O(n)?? you have sorted the array so it would be O(nlogn) already for the sorting so how it would be O(n) for total algorithm??
Girl did 2 sum and 3 sum today!! Keep going, faang is waiting for me
You can do it!
Time complexity is O[n^2logn]. We have to use hashmap apprach of 2 sum if the array is not sorted by default
O(n^2) will be dominant
i got it that
nums.length - 2 in the loop condition is to ensure that there are at least two elements to the right of the current index i
even i can find triplet with for (int i = 0; i < nums.length ; i++) {
insted of
for (int i = 0; i < nums.length -2; i++) {
so is there any reason we are writing -2?
Understood the solution very well. Thank you
Thank you
Perfect
well explained
The code takes 672 Runtime.Whether it is optimal
Good evening sir
Thank you for such a keen explanation. Sir can you do leetcode problems on python 😊
The solution was very simple to understand thankyou so much.
But i had a doubt as I implemented this on leetcode, the time it took for all the test cases was: 457ms , and 9ms solutions were also available. So I have to study the more optimum approach or it is fine for technical round or interview round?
Nice explanation but there are 2 cases over here. if the array is sorted already or the array is not sorted. if the array is sorted we can go with the approach explained by nukhil but if its not sorted the better use hashmap approach which gives O[n] TC and O[N] SC
Great explanation, I just wanted a clarification on the time complexity, i think we left out the time complexity for sorting. What is the time complexity for sorting, otherwise the rest is O(n^2) as explained.
Nice solution, I have now subscribed to your channel, very good explanation and solution. I want to clear Toptal interview, please guide me in some way if possible. Thanks !
good 🤩
you are using a set to arrive at a solution right? so how do you say that you are not using any extra space? or is it just constant space?
it is constant space.
CAN ANYONE EXPLAIN ME WHY HE DID ELSEIF(SUM
You said, for viola in between at 5:22. What does that mean? Just curious
Means kind of ‘wow’ as an exclamation
I dont see what we should sort the array ? if we gonna loop over the loop and everytime fix and try to found a sum that s equal to 0
Sorting the array ensures that all smaller numbers are to the left abd larger to the right.
Then you look at the sum obtained…if greater than target, then you need to pick a smaller number..so just move the right pointer by 1 place instead of traversing the entire array.
Saves you a lot of time.
Nikhil We want 4sum leetcode solution.
nice bro
isme ek problem hai duplicate triplets ko lekr ... triplets double print horhe
How does this solution ensures that we don't use one value multiple times?
because all 3 pointers point at different indexes
13:06 If you're not taking any extra space at all, the space complexity should be O(1)
i misspoke, you are taking the space of the HashSet which has a size (n). Hence O(n).
Thanks for the correction.
does this solution actually work in leetcode? i am getting an error when i submit (not run) the code.
yes it does, check out the complete implementation on the Github link available in video description
Bhaiya, the explanation is so good but we have to skip the duplicate triplets. So, we have to do this
If (i>0 && nums[i]==nums[i-1]){
Continue;
}
Duplicate triplets are the question [-4,-1,-1,0,1,2] are
See the [-1(1 idx),0,1] and [-1(2 idx),0,1]..
Thank you.❤
to skip duplicates thats why he uses hashset
I think one more optimization you can do is this:
Keeping a boolean array of "done" numbers and marking the numbers with which triplets are already made, because there could be duplicates of each number and for each of them you dont have to find the triplets because triplets would be unique,
for example: if there is an array of 3000 integers all containing zero, your code would go to every zero and find the triplets using all zeros whereas the answer would just be [0,0,0]
In this way some cases would be lost as -1, 0,1 and 2,-1, -1 are also there both use -1 and both are different trplets
Bro please bring more video on trees and graph
i am adding more and more videos every week. I am myself limited by resources and time. Hope you understand...if you have a particular topic/question in mind, let me know..and I can add it to my video list.
@@nikoo28 Complete binary search problem series
The complete playlist on graphs is now available: czcams.com/play/PLFdAYMIVJQHNFJQt2eWA9Sx3R5eF32WPn.html
stock market bear bank side
Bro, Your solution is wrong where you are assuming that HashSet will remove duplicate Lists.
{1,2,3} & {3,2,1} are two different lists. They wont be considered duplicate by the HashSet as List equals method wont return equal for both.
Set result = new HashSet();
result.add(Arrays.asList(1, 2, 3));
result.add(Arrays.asList(3, 2, 1));
System.out.println(result.size()); // Prints 2 NOT 1
That is why I sort the array. :)
@@nikoo28 Ok. got it. Since always the sorted List is added to the Set duplicate list addition is taken care of by the Set. But we can optimize the solution to avoid trying to add even those duplicate lists.
int twoSum = A[left] + A[right];
if (twoSum == sum) {
triplets.add(Arrays.asList(A[i], A[left], A[right]));
/**
* Only if we have found a solution for two values we can be sure we should move ahead of all their
* duplicates.
*/
while (left < right && A[left + 1] == A[left]) {
++left;
}
++left;
while (left < right && A[right - 1] == A[right]) {
--right;
}
--right;
}
if you sort the array, you will lost the indices.
But you need to return the values. Not the indexes.
This is not right .. pls check it out it gives duplicate output but in question they asked only unique subsets.. while dry run of your code pls execute in leet code itself ..
check the code available on github in description. It does pass on leetcode.
he is storing it in a HashSet so it won't have duplicates.
Your videos are awesome, thanks for all the details. Can we avoid having the duplicates, like adding memorization? Is that possible?
You are correct. His solution is wrong. it wont remove duplicates.
why are you looking like young Narendra Modi
Jo bhi bolo Hairfall toh bhot hogya 2 saalo me. 😂
can't escaping aging 😅
Sorry to say, but not the best approach.
what would you suggest?
Thanks for the clear explanation, but please note that this solution allows duplicate triplets in the result, which is not correct and won't pass leetcode submission (I tried it myself), here is the correct solution after some changes:
>>> EDIT: When I tried it I was using a LinkedList instead of a HashSet as shown in the video(using HashSet won't allow duplicates indeed and hence the presented solution is correct), anyway here is the correct way to solve it with LinkedList.
class Solution {
public List threeSum(int[] nums) {
Arrays.sort(nums);
List result = new LinkedList();
for (int i = 0; i < nums.length -2; i++) {
if(i == 0 || (i > 0 && nums[i] != nums[i-1])) {
int left = i + 1;
int right = nums.length - 1;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left < right && nums[left+1] == nums[left]) left++;
while(left < right && nums[right-1] == nums[right]) right--;
left++;
right--;
} else if(sum < 0) {
left++;
} else {
right--;
}
}
}
}
return result;
}
} // TC: O(n^2), SC: O(n)
the solution I provided on my github profile does pass leetcode.
Set uses equals and hashcode to compare elements in it, so list1.equals(list2) compares each element sequentially