4 SUM

Find Quads that add up to get a taget value

1. Nested loop TC O(n⁴)
2. Nested loop + set data structure TCo(n³) SC o(n)
3. Sorting +2 pointer approach(3 pointers)TC o(n³) SC o(1)

3 Most Efficient approach

Lets revise some basic concepts

Sorting to faciliate 2 pointer.2 pointer find pairto get third here we use its modified version of 3 pointers.Avoid duplicates skip duplicates to ensure quadruplets are unique.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size(); // size of the array
vector<vector<int>> ans;

Get suhama’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

// If the array has fewer than 4 elements, return an empty answer as we can’t form quadruplets.
if (n < 4) return ans;

// Sort the given array to simplify finding unique quadruplets.
sort(nums.begin(), nums.end());

// Calculating the quadruplets:
for (int i = 0; i < n — 3; i++) {
// Avoid duplicates for the first element
if (i > 0 && nums[i] == nums[i — 1]) continue;

for (int j = i + 1; j < n — 2; j++) {
// Avoid duplicates for the second element
if (j > i + 1 && nums[j] == nums[j — 1]) continue;

// Two-pointer approach for the remaining two elements
int k = j + 1;
int l = n — 1;

while (k < l) {
// Use `long long` to avoid overflow
long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];

if (sum == target) {
// Found a valid quadruplet
ans.push_back({nums[i], nums[j], nums[k], nums[l]});

// Move pointers and skip duplicates
k++;
l — ;

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

} else if (sum < target) {
k++; // Increase sum by moving the left pointer right
} else {
l — ; // Decrease sum by moving the right pointer left
}
}
}
}

return ans;
}
};

Suhama Mustafa