4SUM | GOOGLE | AMAZON

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Leetcode added some test cases, so please use "long long int instead of int for target3 and target2"
.
.
.

[yashwagh]

God that "REMAINING SIX!!" at 11:45. Funny lol. But on a serious note, that actually shows how immersed you are while teaching, great dedication!

[rishisharma]

Nobody :
Striver at 11:45 :
Me : **falls off my chair**

[aryannegi]

we can add a small optimization by changing the stopping conditions of i and j loop as follows :
for(i=0;i<n-3;i++)
for(j=i+1;j<n-2;j++)
alse at the end of these loop the conditions to skip the duplicates can also be changed as follows

}

}
reason same as above reason since if j cant fall in the last two elements since then we cant complete 4 elements and similarly i cant fall in last 3 elements
*Correct me if i am wrong*

[ayushbhagwat]

Use long long int for target_2 and multiply the rhs of that equation by 1LL if you're getting run time error on leetcode.
Line 15: long long int target_2 = 1LL*target - 1LL*nums[ i ] - 1LL*nums[ j ];
Also don't forget to scroll the comment section to find some lil optimizations like in the beginning nums.size() < 4 instead of nums.empty()

I put this here coz I faced some problem while submitting this on leetcode. Glad if it helps.
happy coding :)

[pramodtarpe]

A optimization is to break out of ith for loop if sum is greater than target in sorted nums

[pavitrapatidar]

16:42 Use long data type of target_2 for storing value.
(In Java Solution)

[dhimanarya]

i should be <n-3 and j<n-2 other wise segmentation fault occurs in leetcode, and second mistake is that if nums.size()<4 it should return empty res vector.

[rahulgovindkumar]

Thanks Striver for such Easy and Lucid Explanation and Such a good Placement Series

[mohitkumar-zcwd]

Sir you skipped edge cases for unwanted computations. like if 4*nums[0] > target, then why go into loop;

[darkexodus]

You can directly do res.push_back( {num[i], num[j], num[front], num[back] } ). This pushes a one-dimensional vector of size-4 into vector res.

[AB-tpeg]

Hello bhaiya,
If this can be give a thumbs up please,
I think the extreme brute approach can be in this question use four nested loops, and if we find quadruple having sum=target we will store that quadruple in the hashset (to store the unique quadruples)
TC: O(n^4 logM) --> logM --> for inserting M unique quadruples in the hashset.
SC: O(1)

[sakshisinha]

Please attach the link of the code too.

[codesefod]

His way of explaining and making hard problems easy is awesome. Thank you.

[jatinkumar]

Nice explanation but why space complexity is O(1) in first approach 4:53 when we are using a data structure to store quads and a hashset to retrieve unique quads.

[SjParthi]

Hey Raj, I had a big doubt.
Arrays.sort(int[]) method takes the space complexity of O(logn) when stack frame gets piled up in recursion parts. So if I’m not wrong, we should consider the worst case as O(logn). Please correct me if I’m wrong.

[vishaldubey]

CPP code
21:00
I think else condition is wrong because in the array
1 1 1 2 2 3 3 4 4 4
When i=1
J=2
Front=3
Back=9
Pointer checks v[3]+v[9] is 6 which is less than target_2 i.e 7 so its check for next j instead of skipping that value because we have applied skip condition inside the else
Basically if wali condition Phle hi chl jayegi kyuki 7 se km hai 6 toh else mai jayega nhe or agr else mai nhe gya toh next 2 ko skip kaise krega

[SiddharthDhiman]

in the else block after skipping over duplicates do front++, back-- or the loop will run infinitely

[codingachinilgtifirbhikrrh]

if anybody's wondering about the 3 pointer code:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size()==1)
return {};
sort(nums.begin(), nums.end());
set<vector<int>>ans;
vector<vector<int>>ansar;
for(int i=0;i<nums.size()-2;i++){
for(int j=i+1;j<nums.size();j++){
for(int k=j+1;k<nums.size();k++){
long long no1 = nums[i];
long long no2 = nums[j];
long long no3 = nums[k];
long long ta = target;
long long valTBF = ta - (no1 + no2 + no3);
if(binary_search(nums.begin()+k+1, nums.end(), valTBF)){
ans.insert({nums[i], nums[j], nums[k], (int)valTBF});
}
}
}
}
for(auto i:ans){
ansar.push_back(i);
}
return ansar;
}

[yashsinghania]

Thanks Striver for such Easy and Lucid Explanation and Such a good Placement Series.