4 Sum Problem | Leetcode #18

This video explains a very important programming interview problem which is the 4 sum problem.This problem can be solved using multiple techniques and algorithms.I have explained all the approaches using simple examples.I have explained 3 techniques.The first one is just by using simple set which is the brute force approach.The second technique is by using set with 2 pointer technique. This is the best approach in terms of time complexity. The third approach is by using hashmap.This solution iis better than the naive approach.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

======================================PLEASE DONATE=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

[ayushdhiman]

first time ever saw the face of legend thank you for your tutorials !!

[piyushx]

sir i like prefer these type of videos, as in from the rest of your videos that i saw, this one has your face, and i dont know why but these type of videos where i can see the instructors face, help me have better understanding

[kellie]

you are amazing. thank you for the detailed explanation and clear thought and explanation process.

[Gauravkr]

in second approach, when sum= target u hv written, left=left+1, what if there is duplicate element in while loop also, how to check for dupliacte element in the innermost (while) loop

[sakshamsinghal]

Really! Amazing
One more added in liked video.

[akshaykumarmalathkar]

In the second approach I think we don't need to use a set to handle the duplicates as we can simply compare the last added quadruple with the current one as you did in the 3rd approach.

[kirtikedia]

2nd approach can be done without using set, which will make our time complexity O(n^3) instead of O(n^3)log(n) with this check

while(start < end && arr[start] == arr[start+1]) start++;
while(start < end && arr[end] == arr[end-1]) end--;
This will make sure we don't check 2 sum for same values. Since array is sorted all same values will be adjacent.
So skip the same values until we find new value

Code -


class Solution {
public:
vector<vector<int>> fourSum(vector<int>& arr, int target) {
vector<vector<int>> ans;
int n = arr.size();
if(n<4) return ans;
std::sort(arr.begin(), arr.end());

for(int i=0;i<n-3;i++){
if(i!=0 && arr[i]==arr[i-1]) continue;
for(int j=i+1;j<n-2;j++){
if(j!=i+1 && arr[j] == arr[j-1]) continue;
int find = target - (arr[i]+arr[j]);
int start = j + 1;
int end = n - 1;

while(start < end){
int sum = arr[start] + arr[end];
if(sum == find){
ans.push_back({arr[i], arr[j], arr[start], arr[end]});
while(start < end && arr[start] == arr[start+1]) start++;
while(start < end && arr[end] == arr[end-1]) end--;
start++;
end--;
} else if(sum > find) {
while(start < end && arr[end] == arr[end-1]) end--;
end--;
} else {
while(start < end && arr[start] == arr[start+1]) start++;
start++;
}
}
}
}
return ans;
}
};

[大盗江南]

A question plz. At 5:14, you said that the big O for set operation is O(lg N). is that true ?

Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

For HashMap.containsKey(), it should be O(1) too. right ?

[random]

Hello sir, your explanation is great. I want to know which software are you using to write on the screen. And also what is your set up, like are you using a tablet and writing on it using stylus or you are writing on the laptop using the mouse cursor?

[dogexploresworld]

Thank you!!! This was a great explanation!

[mohammadarif]

This an amazing explanation.
How can i contract with you brother?

[ashwanikumar]

How come insertion in set is LogN. Isn't it amortized O(1)?

[RishavKumar-stpi]

Pls read the leetcode problem carefully. Unique quadruplets doesn't mean unique i, j, k, and l. It means unique n[i], n[j], n[k], and n[l]. Your code is correct but you should have mentioned this way in explanation. Thanks for the answer though.

[MilindGupta]

Sir there is 2 playlist of hash...
One is hashing with 5 videos and one is with more than 10-15 videos...

I have done this 5 video playlist so is the other playlist continuation of this playlist

[hapysethi]

Please explain how the 3 approach takes n^4, I think it takes n^3

[chandragupta]

if make set at last in method 2 then time complexity will be O(n3 +nlogN)=O(n3), am I right?

[xiangao]

some questions about the complexities, for set insertion, hashset insertion should be constant time, isn't it? same constant time for get.
The 3rd approach - generating all the two-sum takes n^2, plus looping through the sums, it's 2* n^2, may not be (n^2 * n ^2)

[sainathreddy]

in method 2 if sum == tar why we are only moving only lefft++, why not r++ or both can anyone explain

[deeptarkoroy]

I have done using the second algorithm.But my set is containing duplicate vectors.How is this possible xD

[atifkhan-ixjc]

I change speed from 2x to normal I was not able to identify his voice