3SUMs

Python solution

C++ solutions

Naive solution (TLE O(n³ log n))

//TLE 311 / 313 test cases passed.
// naive O(n^3 log n) algorithm
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
for (int j=i+1; j < n-1; ++j)
{
for(int k = n-1; k> j;--k)
{
auto sum = nums[i] + nums[j] + nums[k];
if(sum==0)
{
ret.insert(vector<int>{nums[i], nums[j], nums[k]});
}
else if(sum>0)
{
continue;
}
else break;
}
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;

}
};

Binary search solution TLE O(n² log n log n)

//TLE 312 / 313 test cases passed.
// O(n^2 log n log n) algorithm by using binary search
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector<int>{nums[i], nums[j], target});
}

}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;

}
}

O(n² log n) algorithm by using binary search + early pruning + unordered_set

//AC 1080 ms.
// O(n^2 log n) algorithm by using binary search
class Solution {
public:
string vector_to_string(vector<int> v){
string ret = "";
for (auto x:v)ret += to_string(x) + '_';
return ret;
}
vector<int> string_to_vector(string s){
vector<int> ret;
string r="";
for(auto c:s)
{
if (c=='_')
{
ret.push_back(stoi(r));
r = "";
}
else r += c;
}
return ret;
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
unordered_set<string> ret;
for (int i=0; i < n-2; ++i)
{
// early pruning
if (i > 0 && nums[i]==nums[i-1])continue;
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector_to_string(vector{nums[i], nums[j], target}));
}

}
}
vector<vector<int>> fin_ret;
for (auto s: ret)
{
fin_ret.push_back(string_to_vector(s));
}
return fin_ret;
}
};

Binary search solution O(n² log n log n) + early pruning: AC

//AC 780 ms.
// O(n^2 log n log n) algorithm by using binary search
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
// early pruning
if (i > 0 && nums[i]==nums[i-1])continue;
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector<int>{nums[i], nums[j], target});
}

}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};

Improved solution AC O(n² log n)

// runtime 2548 ms
//time complexity O(n^2 log n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.insert(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};

make it faster by early pruning AC O(n² log n)

// jimmy shen//run time 204 ms
// time complexity: O(n^2 log n). We have log n as we are using a set. Add element has the complexity of O(log n). If we use the unordered_map, we will have the complexity of O(n^2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
/**
* The reason that we have the following optimization
* suppose we have two numbers are the same: x, x, y
* then we have 3 cases: 1) x<0 2) x=0 3) x>0
* it's easy to say that x>0 is not OK
* for case 1) and case 2), suppose that we have a pattern x,x,x,x,y,... after carfully analysis, we can get the conclusion that the result based on the first x will contain all the results based on the following repeated x. For example -2, -2, -2, 0, 2, 4. Based on first -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the second -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the third -2, we can get [(-2, 0, 2)]. Hence, we only need collect results based on the first x.

**/
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.insert(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};

We can improve the above solution to O(n²)

//run time 92 ms
// time complexity: O(n^2 ).
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
vector<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
/**
* The reason that we have the following optimization
* suppose we have two numbers are the same: x, x, y
* then we have 3 cases: 1) x<0 2) x=0 3) x>0
* it's easy to say that x>0 is not OK
* for case 1) and case 2), suppose that we have a pattern x,x,x,x,y,... after carfully analysis, we can get the conclusion that the result based on the first x will contain all the results based on the following repeated x. For example -2, -2, -2, 0, 2, 4. Based on first -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the second -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the third -2, we can get [(-2, 0, 2)]. Hence, we only need collect results based on the first x.

**/
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.push_back(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
// we also need to aviod repeating [-2,0,0, 1,1,2, 2]
while (l< r && nums[l+1]==nums[l])l++;
while (l< r && nums[r] == nums[r-1])r--;
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
return ret;
}
};

3SUM advanced

16. 3Sum Closest

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
const int n = nums.size();
int ret = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; ++i){
int l = i + 1, r = n - 1;
while (l < r){
int threeSum = nums[i] + nums[l] + nums[r];
if (abs(threeSum - target) < abs(ret - target)) ret = threeSum;
if (threeSum > target) r--;
else if (threeSum < target) l++;
else return target;
}
}
return ret;
}
};

Reference

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Coding with a K

This is how django and kendo-ui work together

WORLD OF HADOOP ON AWS THROUGH THE PATH OF TERRAFORM (HAT)

15 Day Tech Start-up Launch Plan

Into Game Mechanics: Trigger Cutscene all over the Scene

How to enable ahead-of-time compilation in an Angular hybrid app

Introduction

Vsplit vcam

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Queue Interface In Java

Count the Number of Words in a Word Document Using Java

[LeetCode] (Easy) 35. Search Insert Position

Don’t Forget to do this if you’re using MongoDB | INDEXING