Skip to main content

3Sum

Problem

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.

Solution Approach

Follow a simple Greedy approach. Find all the possible solutions having all the three elements different, two same and one different element, and all the elements are the same. Store the key in a set of vectors to avoid repetition. 

Expected Time complexity: O(n2)O(n^2)

Click - to see solution code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[nums[i]]++;
}

vector<int> arr;
for (auto i : mp) {
arr.push_back(i.first);
}

set<vector<int>> ans;
n = arr.size();
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sm = arr[i] + arr[j];
if (-sm != arr[i] && -sm != arr[j] && mp[-sm] > 0) {
vector<int> v = {arr[i], arr[j], -sm};
sort(v.begin(), v.end());
ans.insert(v);
}
}
}

for (int i = 0; i < n; i++) {
int sm = 2 * arr[i];
if (sm != arr[i] && mp[arr[i]] > 1 && mp[-2 * arr[i]] > 0) {
vector<int> v = {arr[i], arr[i], -sm};
sort(v.begin(), v.end());
ans.insert(v);
}
}

if (mp[0] > 2) {
ans.insert({0, 0, 0});
}
vector<vector<int>> vv;
for (auto i : ans) {
vv.push_back(i);
}
return vv;
}
};