Here’s the question link on LeetCode 15. 3Sum:
https://leetcode.com/problems/3sum/description
Contents
Brute Force O(n³)
The simplest approach is to try every possible combination of three elements.
Use three nested loops, calculate their sum, and if it equals zero, add the triplet to our answer.
But we also need to avoid duplicate triplets. We can sort each triplet and use a set to make sure we only add unique combinations.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
set<vector<int>> st;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; 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);
}
}
}
}
return vector<vector<int>>(st.begin(), st.end());
}
};
Better O(n²) Sorting + Hash Set
Can we avoid the third loop?
Let’s fix one element and find the other two numbers that add up to its negative.
For example, if the fixed number is -1, we need two numbers whose sum is 1.
We can use a hash set to keep track of numbers we’ve already seen.
For every fixed element:
- Calculate the sum we need:
target = -nums[i]. - Traverse the remaining elements.
- Check if
target - nums[j]already exists in our hash set. - If yes, we’ve found a triplet!
- Otherwise, insert the current number into the set.
We’ll sort the array and use a set of triplets to avoid duplicates.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
set<vector<int>> ans;
int n = nums.size();
for(int i = 0; i < n; i++) {
unordered_set<int> seen;
for(int j = i + 1; j < n; j++) {
int need = -nums[i] - nums[j];
if(seen.count(need)) {
ans.insert({nums[i], nums[j], need});
}
seen.insert(nums[j]);
}
}
return vector<vector<int>>(ans.begin(), ans.end());
}
};
Optimal O(n²) Two Pointers
Now, can we avoid the hash set too?
Since the array is already sorted, we can use two pointers!
Here’s the idea:
- Sort the array.
- Fix one element using
i. - Place
leftati + 1andrightat the end. - Calculate the sum of all three elements.
Now:
- If the sum is smaller than zero, move
leftforward to increase the sum. - If the sum is greater than zero, move
rightbackward to decrease the sum. - If the sum is zero, we’ve found our triplet!
We also need to skip duplicate elements so that we don’t add the same triplet multiple times.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for(int i = 0; i < n - 2; i++) {
// Skip duplicate first elements
if(i > 0 && nums[i] == nums[i-1])
continue;
int left = i + 1;
int right = n - 1;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0) {
ans.push_back({
nums[i], nums[left], nums[right]
});
left++;
right--;
// Skip duplicates
while(left < right && nums[left] == nums[left-1])
left++;
while(left < right && nums[right] == nums[right+1])
right--;
}
else if(sum < 0) {
left++;
}
else {
right--;
}
}
}
return ans;
}
};