# 3SUMs

2 SUM is classical. I got stuck on 2 SUM a couple of days ago :(. Now when looking back, 2sum is a toy problem.

3 SUM is classical and not that toy.

Classical 3sum: (leetcode 15. 3Sum)

# Python solution

TLE solution (n²logn)

Pass 311 test cases and failed for longer lists by getting TLE. One of the fail lists has a length of 3000.

Solution 2 (O(n²), 880 ms )

reference

https://leetcode.com/problems/3sum/discuss/7392/Python-easy-to-understand-solution-(O(n*n)-time).

# C++ solutions

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

`//TLE 311 / 313 test cases passed.// naive O(n^3 log n) algorithmclass 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 searchclass 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 searchclass 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 searchclass 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²)

Optimized solution by avoiding repeating AC 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;    }};`

solution 1 (O(N + 101³), 304ms)

solution 1 (O(N + 101²), 120ms)

Trick part:

we can infer the third number c from target and a, b.

However, we need kill the over counter as:

if a + b +c = target,

we can get c from a,b and we can also get b from a,c

for example, when target =8, a, b =1,3 we get c=4

when a, b =1,4 , we get c =3. This will generate over counting.

Using a seen set to kill to over counting.

## 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

https://leetcode.com/problems/3sum/discuss/232712/Best-Python-Solution-(Explained)

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi