Sir,I have one confusion about the time complexity. Inside the innermost loop we have the insert operation in set which take O(logN) in the worst case considering we have n elements inside the side. If we are taking the worst case means that the if(sum==target) is true for each condition.Then Why we are not considering it's complexity. According to my calculation,Time Complexity is O(N^3(logN)). Please sir reply. Thank you in Advance.
@@takeUforward Yes, I watch the all the videos. After the watching video i comment the Timestamp. Recursion and Backtracking series is the one of the best explanation and understanding with your teaching style. I completed 2 days ago.
the way you explain the two pointer approaches and the use of them makes two pointer approach the easiest way to solve a problem. I fell in love the way you are teaching these concepts.
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
Hi Raj, there are 2 slight mistakes in your optimal solution. 1: The 1st for loop will run till n-3 and 2nd for loop will run till n-2 instead of n, because we need to allocate last 2 elements to our two pointers and as per your code when i=n-2, j becomes n-1 (j=i+1=n-2+1) and num[k] throws out of bound exception, because k becomes n(k=j+1) 2: We could also increment low and decrement high when sumtarget respectively until there are duplicates for code to be more optimised. 3: Here's the more readable code(JAVA): class Solution { public List fourSum(int[] nums, int target) { int n = nums.length; List result = new ArrayList(); Arrays.sort(nums); for(int i=0; i
hatsoff bro i was confused for 4 hours for optimal solution that passes all test cases.after seeing your comment it helped me to understand it.thankyou :)
Time Complexity: O(n log n) Space Complexity: O(n) #include #include #include using namespace std; vector fourSum(vector &nums, int target) { // sort the array sort(nums.begin(), nums.end()); // initialize result vector vector result; int n = nums.size(); // iterate through array with two pointers for (int i = 0; i < n; i++) { // skip duplicate elements if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < n - 2; j++) { // skip duplicate elements if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } // use two pointers for remaining elements int left = j + 1; int right = n - 1; while (left < right) { int currentSum = nums[i] + nums[j] + nums[left] + nums[right]; if (currentSum == target) { result.push_back({nums[i], nums[j], nums[left], nums[right]});
// skip duplicate elements while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } // Move pointers left++; right--; } else if (currentSum < target) { // If the sum is less than the target, move the left pointer to the right left++; } else { // If the sum is greater than the target, move the right pointer to the left right--; } } } } return result; } int main() { // Example usage vector nums = {1, 0, -1, 0, -2, 2}; int target = 0; // Call the fourSum function vector result = fourSum(nums, target); // Print the unique quadruplets for (const auto &quadruplet : result) { cout
@@akashchoudhary6876 the overall time complexity of the fourSum function is O(nlogn+n^3)which simplifies to O(n^3)in Big O notation, assuming the input is sufficiently large.
Thank you so much Striver brother, you taught the 3sum and 4sum very clearly. 💀💀 ok jokes apart lol, this series is just too good, i can literally find every concept DSA related a lot of questions of each and every concept.
Though I am little bit late, in this A to Z DSA Playlist But I covered All previous Videos within a week & now just completed 4 Sum. Striver Sir You are great! You will going to create a history in DSA course very soon around all over the World … I don't have the proper words to express my gratitude to you. All the Best Sir God bless you .
@ankitadas5833 hey I would like to know if you have completed entire striver a2z dsa course? If yes, how much time did you take to complete entire course?
if u are stuck at test case 281 in leet code then :- class Solution { public: vector fourSum(vector& nums, int target) { int n =nums.size(); vector ans; sort(nums.begin(),nums.end()); for(auto it:nums) cout
We can excluded the inner while loop for either "k" or "l" index. Incrementing "k" or decrementing "l" would suffice. As one takes care of the other. Updated Solution: '' Optimal Approach - Sorting and 2 Pointers TC = O(nlogn) + O(n^3) = O(nlogn) for sorting + O(n^2) for '2' outer loops * O(n) for inner while loop in their lifetime SC = O(number of quadruplets) for result array Dry Run: nums = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5], target = 8 Possible combinations: [[1,1,1,5],[1,1,2,4],[1,1,3,3],[1,2,2,3]] ''' n = len(nums) nums.sort() result = [] for i in range(0, n): # Ignore duplicate combination if i > 0 and nums[i] == nums[i-1]: continue for j in range(i+1, n): # Ignore duplicate combination if j > i+1 and nums[j] == nums[j-1]: continue l, r = j+1, n-1 while l < r: total = nums[i] + nums[j] + nums[l] + nums[r] if total > target: r -= 1 elif total < target: l += 1 else: # Quadruplet found store = [nums[i], nums[j], nums[l], nums[r]] result.append(store) # Avoid duplicates - Either increment 'l' or decrement 'r' # One takes care of the other l += 1 while l < r and nums[l] == nums[l-1]: l += 1 return result
Code is not running for this test case: nums = [-1, -1, -1] target = -2 if you're writing in a language like C# or Java where lists are considered reference types and the equality are based on references rather than actual values. The workaround in C# is to sort the list like usual and then use a *ValueTuple* to extract the values from the list and then adding this to the set as ValueTuples equality checks are value-based rather than reference which means two different valuetuples with the same numbers in the same order will still be considered as *EQUAL* whereas the same in a list would be considered as *UNEQUAL* due to a difference in references.
It's amazing from brute to better to optimal similarly like 2Sum, 3Sum .. and my doubts in what's about 5-Sum, 6-Sum.. is any universal solution exist?
in the brute force approach when we first added nums[i]+nums[k]+nums[k]+nums[l] and then checked if its == target then it gives integer overflow error regardless of sum being stored in long long variable but if we do it one by one like sum = nums[i]+nums[j] and then sum+=nums[k] and sum+=nums[l] then the error is resolved can anyone please explain to me how its working.
why is it when i use:- long long sum = nums[i]+nums[j]+nums[k]+nums[l] -----it says runtime error but when i use :- long long sum = nums[i]; sum+=nums[j]; sum+=nums[k]; sum+=nums[l]; ----it works fine. Why is that?
@@takeUforward but in 3 sum we sum up like sum = nums[i]+nums[j]+nums[k] but in this 4 sum you sum up all the indices separately which is correct but I am getting error in a test case when I am doing sum = nums[i]+ nums[j]+ nums[k]+ nums[l]; why?
@@SANDEEPKUMAR-in6li the compiler has an algorithm for adding these numbers . while adding four numbers(big numbers) the algorithm needs a lot of space , but while adding two or three the space is under limit. hence adding them one by one is recomended.
while i'm taking sum==target case in else it is not working like we did in three sum and if i put if(sum==target) at initial position it is working . why it is so ?
What about Time complexity for sorting the arrray? I know it will be lesser than N3 in this case. But still good to mention that!. Thanks for putting all the hard word!.
That's bcoz bro there will always be 4 elements that are to be inserted in temp. So the s.c will be O(4) Which will not depend on N i.e. no of elements in vector. And as in S.C we ignore constants.so ignore it
If k crosses l then we have gone through all the possibilities. Imagine this if they crosses each other they will act like each other. After crossing K will give the elements L has already given and the same goes for L
In the better approach why the code didn't gave runtime error for j and k when i = n - 1, because j = i + 1 and k = j + 1, making j and k going out of bounds of array so it should've thrown the error right?
hey, does someone relate with this, i have trouble coming around the solution that i haven't come up with, i overthink and find it hard believing the solution?
Hi, thanks for the video explanation. I had one doubt. When we get the sum==target, we move the k and l pointers front and back respectively [not just once but until we get a different value for k and l pointers so as to not repeat the same ans]. Why are we not doing the same when {sumtarget}. [i.e. in these 2 cases we just do k+=1 or l-=1; shouldn't we here also move the k and l pointers ahead until we get a different value for them.] Please let me know if possible. Thanks!
It goes the same as well. If we move the pointer and again we get the same set , the sum will be the same right ? therefor if the sum is less than zero , it remains the same and vice versa. Then the iteration completes and we will hit the same condition. This goes until we get another pair.
Please watch our new video on the same topic: ruclips.net/video/eD95WRfh81c/видео.html
You said it is O(n3) but sorting will take some time to what about that?
@@uniqueyuvrajgaming3392nlog n is basically negligible in comparision of n3 thats why is it not included
Sir,I have one confusion about the time complexity.
Inside the innermost loop we have the insert operation in set which take O(logN) in the worst case considering we have n elements inside the side.
If we are taking the worst case means that the if(sum==target) is true for each condition.Then Why we are not considering it's complexity.
According to my calculation,Time Complexity is O(N^3(logN)).
Please sir reply.
Thank you in Advance.
@@uniqueyuvrajgaming3392 Sorting will have always 4 elements which will take constant time.
@@TaimoorKhan-h6l do you want to use ordered set?
Note: 0:42 Make sure you watch the 3Sum before doing the 4Sum .
🙂
What if I have seen since a long ago, will it work ?🙃 But why he was laughing while saying this ?
😂😂
naughty audience😂😂😂😂
ok 🙂
0:44 Striver's Smile Says it all
you got my point bro😁
bhai bhai🫡🫡😂. what a detailing bro
Damn I was about to comment this
Hhahahahahahaha
Do give us a like and subscribe, it won't cost you anything, but it will highly motivate us to create more such type of videos :)
striver ..king of DSA
The if condition inside while to check if(k
sir which whiteboard pen app you use for explain the code
hey striver you forgot to add time complexity required for --sorting array --optimal approach so it will be O(NlogN) + O(N^2). plz update
@@codemania2878 He is using an iPad and its default Notes app
Whole video is about 4 sum but 0:40 to 0:50 is wholesome
3 sum was awesome, 4 sum was fantastic!!!!
legends like 5 sum
Ultra Legends like 6 sum
00:54 Problem Statement
02:24 Brute force approach
03:08 Code
05:38 Complexity
06:14 Better approach
11:31 Code
13:22 Complexity
14:54 Optimal approach
21:59 Code
27:04 Complexity
You watch all the videos? I see you daily updating me with timestamps, massive thanks for that.
@@takeUforward Yes, I watch the all the videos. After the watching video i comment the Timestamp.
Recursion and Backtracking series is the one of the best explanation and understanding with your teaching style. I completed 2 days ago.
@@takeUforward striver please update timestamp in disucssion so that ppl can access it easily
Excited to do 4sum after completing 3sum yesterday
Damn bro include me next time
@@gareer2436 you know how to bend?😂😂
Yaar tum log bohat tharki ho 😂
@@yashsharma6396 no but I know what to do when someone bends...😏
Lay them down and..
Massage their backs of course!
@@gregorirasputin659 ma to sath me problem solve krne ki baat kr raha tha bro... tum kya soch liye?😏
Finally did 4 sum, amazing experience
Can you elaborate your experience? Asking for a friend
can you explain about your experience...🙂🙂
@@catalyst8654 🤣🤣
Would you take a moment to share your experience with us.
The problem right? RIGHT??
You should not take I upto
it doesn't create a big difference
the way you explain the two pointer approaches and the use of them makes two pointer approach the easiest way to solve a problem. I fell in love the way you are teaching these concepts.
The consistency level of striver is really the source of motivation 🔥.
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.
Hi Raj, there are 2 slight mistakes in your optimal solution.
1: The 1st for loop will run till n-3 and 2nd for loop will run till n-2 instead of n, because we need to allocate last 2 elements to our two pointers and as per your code when i=n-2, j becomes n-1 (j=i+1=n-2+1) and num[k] throws out of bound exception, because k becomes n(k=j+1)
2: We could also increment low and decrement high when sumtarget respectively until there are duplicates for code to be more optimised.
3: Here's the more readable code(JAVA):
class Solution {
public List fourSum(int[] nums, int target) {
int n = nums.length;
List result = new ArrayList();
Arrays.sort(nums);
for(int i=0; i
hatsoff bro i was confused for 4 hours for optimal solution that passes all test cases.after seeing your comment it helped me to understand it.thankyou :)
@@_Arunvfx glad you finally understood it. Keep pushing forward 😃
Afaik, it won't throw out of bound exception, because there is a check being done (k < l). In ur case, k takes n and l takes n - 1.
bro couldn't control his laugh during 3sum , 4sum intro and had to cut the clip 🤣
fell in love with your way of explanation❤
Time Complexity: O(n log n)
Space Complexity: O(n)
#include
#include
#include
using namespace std;
vector fourSum(vector &nums, int target)
{
// sort the array
sort(nums.begin(), nums.end());
// initialize result vector
vector result;
int n = nums.size();
// iterate through array with two pointers
for (int i = 0; i < n; i++)
{
// skip duplicate elements
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
for (int j = i + 1; j < n - 2; j++)
{
// skip duplicate elements
if (j > i + 1 && nums[j] == nums[j - 1])
{
continue;
}
// use two pointers for remaining elements
int left = j + 1;
int right = n - 1;
while (left < right)
{
int currentSum = nums[i] + nums[j] + nums[left] + nums[right];
if (currentSum == target)
{
result.push_back({nums[i], nums[j], nums[left], nums[right]});
// skip duplicate elements
while (left < right && nums[left] == nums[left + 1])
{
left++;
}
while (left < right && nums[right] == nums[right - 1])
{
right--;
}
// Move pointers
left++;
right--;
}
else if (currentSum < target)
{
// If the sum is less than the target, move the left pointer to the right
left++;
}
else
{
// If the sum is greater than the target, move the right pointer to the left
right--;
}
}
}
}
return result;
}
int main()
{
// Example usage
vector nums = {1, 0, -1, 0, -2, 2};
int target = 0;
// Call the fourSum function
vector result = fourSum(nums, target);
// Print the unique quadruplets
for (const auto &quadruplet : result)
{
cout
kuch bhi, same solution hai upar wala time complexity n3 hai, apki nlogn kaise aa gayi
@@akashchoudhary6876 the overall time complexity of the fourSum function is O(nlogn+n^3)which simplifies to O(n^3)in Big O notation, assuming the input is sufficiently large.
@@akashchoudhary6876 sorting in cpp will take O(nlogn)
@@akashchoudhary6876 hahahahah
Understood,Thanks striver for this amazing video.
wow,....wow....wah..awesome expaination. undestood bro..hatsoff to you.
Thank you so much Striver brother, you taught the 3sum and 4sum very clearly. 💀💀
ok jokes apart lol, this series is just too good, i can literally find every concept DSA related a lot of questions of each and every concept.
Thanks for clearing my concepts
Though I am little bit late, in this A to Z DSA Playlist But I covered All previous Videos within a week & now just completed 4 Sum. Striver Sir You are great! You will going to create a history in DSA course very soon around all over the World … I don't have the proper words to express my gratitude to you. All the Best Sir God bless you .
@@ArjunS-hi3vl Yes
have you completed the course ? im also quite late in starting the course and moving at about the same pace as you
@ankitadas5833 hey I would like to know if you have completed entire striver a2z dsa course? If yes, how much time did you take to complete entire course?
Ahaaa... excellent explanation 😊
uffffffff.... understood , bahut bhala se bujhi hela bhai
People who are aware of 2 pointer approach, watch from 14:56, saves a lot of time.
best explanation on you tube
understood, thanks for the perfect explanation
Thanks a ton for explaining in simplest way 🙏🙏🙏🙏🙏🙏
This has to be the horniest coding problem 🌚
😂😂😂😂
Awesome Lecture Sir............
Striver..... you are amazing.................................... Thanks so much bro
if u are stuck at test case 281 in leet code then :-
class Solution {
public:
vector fourSum(vector& nums, int target) {
int n =nums.size();
vector ans;
sort(nums.begin(),nums.end());
for(auto it:nums)
cout
Understood beautifully!! 🔥❤
Great bhaiya ❤️🇮🇳 , ready for next one
I have done this question using subsequence technique thanks u raj sir 😊 u teach really simple
understood,thnx for the amazing video ❤❤❤❤👌👌💕💕
Thankyou for the wonderful series ❤️🔥
Understood!! Thanks for the nice explanation
23:16 shouldnt j= i+1 will be second element? I cant understand
bro couldnt help but smile 0:42
Striverr bhai ke liye toh 10some bhi asaan hai...Jokes apart hes the best teacher on youtube
We can excluded the inner while loop for either "k" or "l" index. Incrementing "k" or decrementing "l" would suffice. As one takes care of the other.
Updated Solution:
''
Optimal Approach - Sorting and 2 Pointers
TC = O(nlogn) + O(n^3)
= O(nlogn) for sorting +
O(n^2) for '2' outer loops * O(n) for inner while loop in their lifetime
SC = O(number of quadruplets) for result array
Dry Run:
nums = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5], target = 8
Possible combinations:
[[1,1,1,5],[1,1,2,4],[1,1,3,3],[1,2,2,3]]
'''
n = len(nums)
nums.sort()
result = []
for i in range(0, n):
# Ignore duplicate combination
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n):
# Ignore duplicate combination
if j > i+1 and nums[j] == nums[j-1]:
continue
l, r = j+1, n-1
while l < r:
total = nums[i] + nums[j] + nums[l] + nums[r]
if total > target:
r -= 1
elif total < target:
l += 1
else:
# Quadruplet found
store = [nums[i], nums[j], nums[l], nums[r]]
result.append(store)
# Avoid duplicates - Either increment 'l' or decrement 'r'
# One takes care of the other
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
return result
at 6 : 10 : i think for computing space complexity, we only compute space required by the algorithm. we don't add space taken by the result
Amazing, thankyou!
helpful to understand integer overflow
Code is not running for this test case:
nums =
[-1, -1, -1]
target = -2
if you're writing in a language like C# or Java where lists are considered reference types and the equality are based on references rather than actual values. The workaround in C# is to sort the list like usual and then use a *ValueTuple* to extract the values from the list and then adding this to the set as ValueTuples equality checks are value-based rather than reference which means two different valuetuples with the same numbers in the same order will still be considered as *EQUAL* whereas the same in a list would be considered as *UNEQUAL* due to a difference in references.
It's amazing from brute to better to optimal similarly like 2Sum, 3Sum .. and my doubts in what's about 5-Sum, 6-Sum.. is any universal solution exist?
Yes, the complexity will keep on increasing tho
After doing 4 Sum.... I think Sky is the limit 🌝
Sir app apne resume k project me konsa tech stack use kya haii. ❤ love your videos
Understood! Super wonderful explanation as always, thank you so so much for your effort!!
Nice explanation. But the title is a bit too sus don't you think?
in the brute force approach when we first added nums[i]+nums[k]+nums[k]+nums[l] and then checked if its == target then it gives integer overflow error regardless of sum being stored in long long variable but if we do it one by one like sum = nums[i]+nums[j] and then sum+=nums[k] and sum+=nums[l] then the error is resolved can anyone please explain to me how its working.
did you found how does it works ? same doubt here
Thank you bro. Understood
why is it when i use:-
long long sum = nums[i]+nums[j]+nums[k]+nums[l]
-----it says runtime error but when i use :-
long long sum = nums[i];
sum+=nums[j];
sum+=nums[k];
sum+=nums[l];
----it works fine. Why is that?
24:23 why not sum = nums[i] + nums[j] + nums[k] + nums[l] ?
can anyone explain plz
you can but you may may get an error!!
excellent question....
Understood 🙏🏻
Understood !!!!!
Why aren't we considering the TC for inserting the vector in the set in brute and better approach ? Please lmk what I'm missing
becoz for inserting and getting the element in set is o(1) just ignoring that....
its particularly constant because we are only storing quad's generated
you are the best 🧿🧿
04:20 - what does exceeding the integer limit mean? (when we are storing it in a long long)
if you store in int it might exceed
@@takeUforward but in 3 sum we sum up like sum = nums[i]+nums[j]+nums[k] but in this 4 sum you sum up all the indices separately which is correct but I am getting error in a test case when I am doing sum = nums[i]+ nums[j]+ nums[k]+ nums[l]; why?
@@SANDEEPKUMAR-in6li the compiler has an algorithm for adding these numbers . while adding four numbers(big numbers) the algorithm needs a lot of space , but while adding two or three the space is under limit. hence adding them one by one is recomended.
Aaj maza aa gya 3 sum karke🌚🌚🌚 ab 4 sum krunga
When striver submits on Code Studio , it also showed him time complexity as O(n4 log n) but it doesn't show in mine. Why?
Imagine someone getting your video, on Searching 3sum video or 4sum video on google 🌚😂
Optimal Orgasm 🤣
😂😂
Bhaiya is everything fine any health issues video is not coming ??
Amazing Explanation
I think first i should learn 3SUM then will do 4SUM as you said
Please learn 2 sum, then 3 sum, then only 4 sum should be implemented ! Yes in terms of problem.
@@takeUforward 😂😂
@@takeUforward 🤣🤣🤣
@@takeUforward sir but partner is not available how to do 2sum
I am still with 1sum
while i'm taking sum==target case in else it is not working like we did in three sum and if i put if(sum==target) at initial position it is working . why it is so ?
Thank you!
Understood ❤
We should consider the time complexity for sorting the given array right ?
Nice to do 4 sum.
thank you sir
What about Time complexity for sorting the arrray? I know it will be lesser than N3 in this case. But still good to mention that!. Thanks for putting all the hard word!.
understood ❤
28.10 are we not using the space for vector temp = { , , , }; line no. 18 ??
That's bcoz bro there will always be 4 elements that are to be inserted in temp.
So the s.c will be O(4)
Which will not depend on N i.e. no of elements in vector.
And as in S.C we ignore constants.so ignore it
@@ictfan-ly8gh got the point, thanks.
why we are putting condition while(k
If k crosses l then we have gone through all the possibilities. Imagine this if they crosses each other they will act like each other. After crossing K will give the elements L has already given and the same goes for L
Thxu striver bhai 😊😊
Just wanted to add the Time Complexity will also contain log(n) since we are sorting the array, right?
understood , thank you!
Understood 💯💯💯
Understood🤙
Understood!
Why removing duplicates I'm not getting the concept in 3 sum problem too in optimal solution
In the better approach why the code didn't gave runtime error for j and k when i = n - 1, because j = i + 1 and k = j + 1, making j and k going out of bounds of array so it should've thrown the error right?
while starting for loop we also stated j and k should be less than n if it goes out of bound whole loop will end.. so no chance
@@statuscreation9493 ohh got it thankyou bro
easy peasy✨✨
The complexity of better solution is n^4 *logn according to codestudio
thank you
Thanks Lord
Understood 🎉
understood bhaiya
For optimal solution time complexity, we have to add sort() time too ig
understood !
hey, does someone relate with this, i have trouble coming around the solution that i haven't come up with, i overthink and find it hard believing the solution?
understood👍
understood sir
Understood Srtiver!
Understood ❤️
Understood.
Hi, thanks for the video explanation. I had one doubt. When we get the sum==target, we move the k and l pointers front and back respectively [not just once but until we get a different value for k and l pointers so as to not repeat the same ans]. Why are we not doing the same when {sumtarget}. [i.e. in these 2 cases we just do k+=1 or l-=1; shouldn't we here also move the k and l pointers ahead until we get a different value for them.] Please let me know if possible. Thanks!
It goes the same as well. If we move the pointer and again we get the same set , the sum will be the same right ? therefor if the sum is less than zero , it remains the same and vice versa. Then the iteration completes and we will hit the same condition. This goes until we get another pair.