DSA
3 Sum
Covers: Brute Force, Better, Optimal. Optimal — Time O(nlogn), Space O(t).
Practice Link
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Brute Force#
Use three nested loops to enumerate every combination of three indices. When their sum equals 0, sort the triple and insert it into a set to deduplicate. The O(n³) time is too slow for large inputs.
Check all combinations of 3 elements Use set to maintain unique triplets
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> st;
for(int i=0;i<nums.size();i++)
{
for(int j=i+1;j<nums.size();j++)
{
for(int k=j+1;k<nums.size();k++)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> temp = {nums[i], nums[j],nums[k]};
sort(temp.begin(), temp.end());
st.insert(temp);
}
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
};
Time Complexity - O(n^3) --> Gives TLE
Space Complexity - O(2*t) , where t is the number of unique triplets
Better Approach#
Fix the first two elements with two loops. The required third element is -(nums[i] + nums[j]). Look it up in a hash set built from elements seen so far in the inner loop. This eliminates the third loop, reducing time to O(n²). A set still deduplicates triplets, adding a log factor per insert. Still too slow for the largest inputs due to the set overhead and constant factors.
Remove the third loop by Using a hashset with a[k] = -(a[i] + a[j])
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> st;
for(int i=0;i<nums.size();i++)
{
set<int> hash;
for(int j=i+1;j<nums.size();j++)
{
int third = -(nums[i] + nums[j]);
if(hash.find(third) != hash.end())
{
vector<int> temp = {nums[i], nums[j], third};
sort(temp.begin(), temp.end());
st.insert(temp);
}
hash.insert(nums[j]);
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
};
Time Complexity - O(n^2) --> gives TLE
Space Complexity - O(2*t) + O(n), where t is the number of unique triplets
Optimal Approach#
Sort the array. Fix the first element nums[i] (skip duplicates). Then use two pointers left = i+1 and right = n-1 to find pairs that sum to -nums[i]. If the three-sum is too small move left right; if too large move right left; if equal record the triplet and skip duplicate values for both pointers. Sorting enables the two-pointer sweep in O(n) per outer step, giving O(n²) total with no hash-set overhead.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i=0;i<nums.size();i++)
{
if(i>0 && nums[i]==nums[i-1])
continue;
int left = i+1;
int right = nums.size()-1;
while(left<right)
{
int sum = nums[i] + nums[left]+nums[right];
if(sum<0)
left++;
else if(sum>0)
right--;
else{
ans.push_back({nums[i], nums[left], nums[right]});
while(left<nums.size()-1 && nums[left]==nums[left+1])
left++;
while(right>0 && nums[right]==nums[right-1])
right--;
left++;
right--;
}
}
}
return ans;
}
};
Time Complexity - O(n^2) + O(nlogn) -> for sorting
Space Complexity - O(t) where t is the number of unique triplets