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.
@@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.
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??
This is a good solution but the use of Set and then copying it back into a list is increasing the time complexity further, you fail to take that into account, on leetcode this solution takes more than 800ms which will not be good enough to clear the interview where they are expecting the optimal solution. Maybe you should also post how well your solutions perform compared to others on leetcode.
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
@@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; }
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.
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 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 !
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
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.❤
After seeing lot many videos, finally I found the crystal clear approach.. Thank you so much brother. One question, how you handle the duplicate element in this?
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.
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.
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 ..
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]
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)
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
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??
Using a HashMap, the complexity for TwoSum will be O(N). Without sorting only it can be done.
i think the same thing, TC should be O(nlogn) + O(n) , SC= O(n)
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
why are you looking like young Narendra Modi
The code takes 672 Runtime.Whether it is optimal
Beautifully explained 😊
Nikhil We want 4sum leetcode solution.
you did well soldier,nice approach simple and elegant but the duplicates numbers in arrays has to skipped to increase the faster execution
This is a good solution but the use of Set and then copying it back into a list is increasing the time complexity further, you fail to take that into account, on leetcode this solution takes more than 800ms which will not be good enough to clear the interview where they are expecting the optimal solution. Maybe you should also post how well your solutions perform compared to others on leetcode.
Damn, this video made the problem super easy
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
@@nikoo28 we are sorting the array so complexity should be 0(n2 logn)
Notice that the solution set must not contain duplicate triplets. Your solution will return duplicate triplets. For example: [-2,0,0,2,2]
we do handle duplicates. What output did you get with this test case?
CAN ANYONE EXPLAIN ME WHY HE DID ELSEIF(SUM
as he explained we need to adjust the index as per the sum
ex- if sum
Simple ,yet optimized , thanks Nikhil!
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;
}
what about edge cases
like all +ve or all -ve or all 0
where you have to return {}, {}, {0,0,0} respectively
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.
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 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 !
How does this solution ensures that we don't use one value multiple times?
because all 3 pointers point at different indexes
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
Amazing explanation. You redefined the meaning of comprehensive😎
Really appreciate the effort you put into making other people understand. It is great service.
stock market bear bank side
thanks for your fantastic explaination with simple code.
Perfect
Thank you ... ❤
Thank you
Thanks Brother
isme ek problem hai duplicate triplets ko lekr ... triplets double print horhe
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
Best approach.
After seeing lot many videos, finally I found the crystal clear approach.. Thank you so much brother. One question, how you handle the duplicate element in this?
I am using a HashSet, that takes care of duplicates
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.
but how to handl eduplicates
that is why a hashset is used
thnks
Nice explanation, setup and video quality 📸
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
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.
Good evening sir
Thank you for such a keen explanation. Sir can you do leetcode problems on python 😊
You said, for viola in between at 5:22. What does that mean? Just curious
Means kind of ‘wow’ as an exclamation
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.
Great solution ..understandable
Too good , Thank you for sharing your knowledge
glad i could help you!!
thank you bhaiya , i was stuck in this since yesterday
Girl did 2 sum and 3 sum today!! Keep going, faang is waiting for me
You can do it!
if you sort the array, you will lost the indices.
But you need to return the values. Not the indexes.
great man
Amazing explanation 🔥
Thank you 🙌 😄
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
Perfect Video !!!
dil se pyaar aapko sir
well explained
Very Excellent solution, was stuck in this prob for hrs
glad I could help
Easy to understand!!!
great
great explanation
Jo bhi bolo Hairfall toh bhot hogya 2 saalo me. 😂
can't escaping aging 😅
Great work Nikhil
nice bro
You explain very well 👏
good 🤩
Crystal Clear Explanation Sir
very nice explanation, before that i went through couple of video to understand properly but this time I understood . Thanks.
glad I could help
great explanation, congratulations on putting in this effort!!!
Glad you enjoyed it!
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: th-cam.com/play/PLFdAYMIVJQHNFJQt2eWA9Sx3R5eF32WPn.html
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.
Understood the solution very well. Thank you
Sorry to say, but not the best approach.
what would you suggest?
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
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
The best and simplest explanation and code I found on TH-cam 🥹 thank you so much sir