4 Sum | Brute - Better - Optimal with Codes

We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.

You can follow me across social media, all my handles are below:

0:00 Introduction of Course
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

[shailesh_rajpurohit]

Note: 0:42 Make sure you watch the 3Sum before doing the 4Sum .
🙂

[takeUforward]

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 :)

[yashsharma]

Excited to do 4sum after completing 3sum yesterday

[ashishashish]

Whole video is about 4 sum but 0:40 to 0:50 is wholesome

[jatinsareen]

3 sum was awesome, 4 sum was fantastic!!!!

[arujgarg]

Finally did 4 sum, amazing experience

[selvaarumugam]

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.

[shubhamagarwal]

#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.

[mehulthuletiya]

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

[cinvest]

You should not take I upto <n, you can just stop i at<n-3 and for j<n-2. No need to check further

[impalash_ag]

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 sum<target and sum>target respectively until there are duplicates for code to be more optimised.
3: Here's the more readable code(JAVA):

class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);

for(int i=0; i<n-3; i++) {
if(i==0 || nums[i]!=nums[i-1]) {

for(int j=i+1; j<n-2; j++) {
if(j==i+1 || nums[j]!=nums[j-1]) {

twoSum(nums, i, j, result, target);
}
}
}
}
return result;
}

public void twoSum(int[] nums, int i, int j, List<List<Integer>> result, long target) {
int low = j+1, high = nums.length-1;
Long sum = null;

while(low < high) {
sum =

if(sum < target) {
low++;
while(low<high && nums[low]==nums[low-1])
low++;
} else if(sum > target) {
high--;
while(high>low && nums[high]==nums[high+1])
high--;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
low++;
high--;
while(low<high && nums[low]==nums[low-1])
low++;
while(high>low && nums[high]==nums[high+1])
high--;
}
}
}
}

[dishankbaid]

The consistency level of striver is really the source of motivation 🔥.

[shubhrajyotipoddar]

bro couldn't control his laugh during 3sum, 4sum intro and had to cut the clip 🤣

[hareshnayak]

Understood, Thanks striver for this amazing video.

[THUNDER-kwwq]

Striverr bhai ke liye toh 10some bhi asaan hai...Jokes apart hes the best teacher on youtube

[AbhimanyuKumar-pwje]

if u are stuck at test case 281 in leet code then :-

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n =nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(auto it:nums)
cout<<it <<" ";
for(int i=0;i<n;i++)
{
if(i>0 && nums[i]==nums[i-1])continue;
for(int j=i+1;j<n;j++)
{ // j!= i+1 first element we have to skip
if(j!=i+1 && nums[j]==nums[j-1])continue;
int k=j+1;
int l=n-1;
while(k<l)
{
long long sum=nums[i];
sum+=nums[j];
sum+=nums[k];
sum+=nums[l];
if(sum<target)k++;
else if(sum>target)l--;
else
{
vector<int> tmp={nums[i], nums[j], nums[k], nums[l]};

ans.push_back(tmp);

while(k<l && nums[k]==nums[k+1])k++;
while(k<l && nums[l]==nums[l-1])l--;
k++;
l--;
}

}
}
}

return ans ;


}
};

[kaichang]

understood, thanks for the perfect explanation

[omkarsawant]

Time Complexity: O(n log n)
Space Complexity: O(n)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int> &nums, int target)
{
// sort the array
sort(nums.begin(), nums.end());
// initialize result vector
vector<vector<int>> 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<int> nums = {1, 0, -1, 0, -2, 2};
int target = 0;

// Call the fourSum function
vector<vector<int>> result = fourSum(nums, target);
// Print the unique quadruplets
for (const auto &quadruplet : result)
{
cout << "[ ";
for (int num : quadruplet)
{
cout << num << " ";
}
cout << " ]\n";
}

return 0;
}

[praveennemagoudar]

wow, ....wow....wah..awesome expaination. undestood bro..hatsoff to you.

[MdKaif-bfnz]

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.