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??
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.
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 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
Using Hashet increases the time a lot we are gettinh 800 ms execution time. we can use below to reduce it. class Solution { public List threeSum(int[] nums) {
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.❤
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 !
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; }
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.
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]
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 ..
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)
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
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
Simple ,yet optimized , thanks Nikhil!
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)
Really appreciate the effort you put into making other people understand. It is great service.
Thank you very much for your clear explanations and for drawing things out.
Amazing explanation. You redefined the meaning of comprehensive😎
Best explanation I've watched. Thank you!
Awesome, thank you!
Waouh, I was really lost with that problem but you explained it so well that I understand now. Thanks!
I liked your way of teaching. Subscribed!!
I'm glad you liked it. More videos coming soon!
very nice explanation, before that i went through couple of video to understand properly but this time I understood . Thanks.
glad I could help
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)
I think sorting us just done once so nsquared + logn which reduces to n2
Beautifully explained 😊
thanks for your fantastic explaination with simple code.
you did well soldier,nice approach simple and elegant but the duplicates numbers in arrays has to skipped to increase the faster execution
Thankyou sir, great explanation i understood very well
Damn, this video made the problem super easy
Girl did 2 sum and 3 sum today!! Keep going, faang is waiting for me
You can do it!
Thanks for video , can you explain this problem -4 Sum - Find any quadruplet having given sum.
Too good , Thank you for sharing your knowledge
glad i could help you!!
Very Excellent solution, was stuck in this prob for hrs
glad I could help
Best approach.
great explanation, congratulations on putting in this effort!!!
Glad you enjoyed it!
Nice explanation, setup and video quality 📸
one of the best UA-camr
Thanks Sir For Solution
You said, for viola in between at 5:22. What does that mean? Just curious
Means kind of ‘wow’ as an exclamation
How does this solution ensures that we don't use one value multiple times?
because all 3 pointers point at different indexes
Amazing explanation 🔥
Thank you 🙌 😄
The code takes 672 Runtime.Whether it is optimal
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
Well explained❤ helpful!!!!
The best and simplest explanation and code I found on UA-cam 🥹 thank you so much sir
Crystal Clear Explanation Sir
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
what about edge cases
like all +ve or all -ve or all 0
where you have to return {}, {}, {0,0,0} respectively
thank you bhaiya , i was stuck in this since yesterday
Great work Nikhil
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.
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?
Great solution ..understandable
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.
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.
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
Using Hashet increases the time a lot we are gettinh 800 ms execution time.
we can use below to reduce it.
class Solution {
public List threeSum(int[] nums) {
if(nums.length
dil se pyaar aapko sir
Perfect Video !!!
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
You explain very well 👏
isme ek problem hai duplicate triplets ko lekr ... triplets double print horhe
Thank you ... ❤
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
Understood the solution very well. Thank you
Easy to understand!!!
great
great explanation
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
but how to handl eduplicates
that is why a hashset is used
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 !
Thanks Brother
Nikhil We want 4sum leetcode solution.
great man
Thank you
Good evening sir
Thank you for such a keen explanation. Sir can you do leetcode problems on python 😊
well explained
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.
Perfect
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;
}
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: ua-cam.com/play/PLFdAYMIVJQHNFJQt2eWA9Sx3R5eF32WPn.html
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?
thnks
good 🤩
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
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.
if you sort the array, you will lost the indices.
But you need to return the values. Not the indexes.
why are you looking like young Narendra Modi
stock market bear bank side
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