15 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Attempt 1: Brute force, O(N^3 + 2NlogN), O(N) space, TLE

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> threeSum;

    if (nums.size() < 3) return threeSum;
    sort(nums.begin(), nums.end());
    vector<int> temp(3);

    for (int counter1 = 0; counter1 < nums.size(); counter1++) {
        for (int counter2 = counter1 + 1; counter2 < nums.size(); counter2++) {
            for (int counter3 = counter2 + 1; counter3 < nums.size(); counter3++) {
                if (nums.at(counter1) + nums.at(counter2) + nums.at(counter3) == 0) {
                    temp[0] = (nums.at(counter1));
                    temp[1] = (nums.at(counter2));
                    temp[2] = (nums.at(counter3));
                    threeSum.push_back(temp);
                }
            }
        }
    }

    sort(threeSum.begin(), threeSum.end());
    threeSum.erase(unique(threeSum.begin(), threeSum.end()), threeSum.end());

    return threeSum;
}

Attempt 2: TLE

• The idea is that if we sort our array, we'll be able to inch our way closer to the solution.

• We maintain three 'pointers', main, iter, and max - and control where these point to depending on the current sum.

  • If the current sum is negative, then we check the next combination that will make the next current sum less negative. We do this by incrementing the iterator.

  • If the current sum is greater than zero, then we have overestimated. Decrementing the max index will ensure that the next current sum will be less positive.

  • When we find a result, then the iterator should increment to find the next unique solution. However, because we know that doing so will make the next current sum positive, we counter act that by decrementing max.

  • A set is used to maintain uniqueness.

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> comb_sums;
    set<vector<int>> unique_add;
    vector<int> temp;
    if (nums.size() < 3) return comb_sums;

    sort(nums.begin(), nums.end());

    int cur_sum;
    int main, iter, max;

    for (int main = 1; main <= nums.size(); main++) {        
        iter = main + 1;
        max = nums.size() - 1;

        while (max >= iter) {
            cur_sum = nums.at(main - 1) + nums.at(iter - 1) + nums.at(max);

            if (cur_sum == 0) {
                temp.push_back(nums.at(main - 1));
                temp.push_back(nums.at(iter - 1));
                temp.push_back(nums.at(max));
                unique_add.insert(temp);
                temp.clear();
                iter++;
                max--;
            }
            else if (cur_sum < 0) {
                iter++;
            }
            else // cur_sum > 0 
                max--;
        }
    }

    for (auto &i : unique_add) {
        comb_sums.push_back(i);
    }

    return comb_sums;
}


int main() {
    vector<int> nums = {1,2,3,4,5,6};
    print2d(threeSum(nums));

    nums = { -1, 0, 1, 2, -1, -4 };
    print2d(threeSum(nums));
}

Attempt 3: O(n^2), TLE

• Approach:

  • I applied that same idea in 2Sum, which runs O(n).

  • In 2sum, the idea what to iterate through the array and find a valid target, which if a + b = target, then we hash to try and find a = target - b.

  • In 3sum, I took the same approach. If a + b + c = target, then I hash to find a + b = target - c.

    • Now I'll have to iterate through permutational pairs of a and b, which will take O(n^2) with a double for loop.

    • I ensure that the second for loop never overlaps with the first and avoids duplicates by having it set to j = i + 1.

    • In over to find all pair triplets that sum to zero and avoid duplicates at the same time, I used to two checks:

      • The first, is is_valid_number, which check for a few things. One, the number target - c or -(a + b) must exist in the hash table. And secondly, if it does and there are duplicates, e.g. -1,-1,2, where a=b, then it must also mean that the occurrences for -1 must be > 2. Likewise if -1,2,-1, then target = a, so the occurrences must be greater than 1.

    • Secondly, I maintain a Permutation unordered_set that captures only unique triples in O(1) time. The idea for this is explained in my other gitbook, chapter Hash by Custom Object.

struct Permutation
{
    Permutation(int _a, int _b, int _c) {
        a = _a; b = _b; c = _c;
    }

    int a, b, c;
};

inline bool operator == (Permutation const& lhs, Permutation const& rhs)
{
    return (( (lhs.a == rhs.a) && (lhs.b == rhs.b) && (lhs.c == rhs.c) ) ||
            ( (lhs.a == rhs.a) && (lhs.b == rhs.c) && (lhs.c == rhs.b) ) ||
            ( (lhs.a == rhs.b) && (lhs.b == rhs.a) && (lhs.c == rhs.c) ) ||
            ( (lhs.a == rhs.b) && (lhs.b == rhs.c) && (lhs.c == rhs.a) ) || 
            ( (lhs.a == rhs.c) && (lhs.b == rhs.a) && (lhs.c == rhs.b) ) || 
            ( (lhs.a == rhs.c) && (lhs.b == rhs.b) && (lhs.c == rhs.a) ));
}

struct Hash 
{
    size_t operator() (const Permutation &p) const {
        int permutation_hash = p.a + p.b + p.c;
        return permutation_hash;
    }
};

bool is_valid_number(const unordered_map<int, int> &num_freq, int i, int j)
{
    int look_for = -(i + j);
    if (num_freq.find(look_for) == num_freq.end()) return false;
    else if (i == j) return num_freq.at(look_for) > 2;
    else if (look_for == i) return num_freq.at(i) > 1;
    else if (look_for == j) return num_freq.at(j) > 1;
    return true;
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        // store occurances and frequencies
        unordered_map<int, int> num_freq;
        num_freq.reserve(nums.size());
        for (int i : nums) {
            if (num_freq.find(i) == num_freq.end()) {
                num_freq.insert(make_pair(i, 1));
            }
            else num_freq[i]++;
        }

        vector<vector<int>> zero_sums;
        unordered_set<Permutation, Hash> only_combs;
        only_combs.reserve(nums.size());

        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                Permutation temp(nums[i], nums[j], -(nums[i] + nums[j]));

                if (is_valid_number(num_freq, nums[i], nums[j])
                    && only_combs.find(temp) == only_combs.end()) {

                    zero_sums.push_back({ nums[i], nums[j], -(nums[i] + nums[j]) });
                    only_combs.insert(temp);

                }
            }
        }

        return zero_sums;
    }
};


int main()
{

    Solution s;
    vector<int> test = { -1, 0, 1, 2, -1, -4};
    vector<vector<int>> sum3 = s.threeSum(test);
    print2d(sum3);

    vector<int> test2 = { 13,-11,-14,4,-9,-10,-11,7,-14,-9,14,0,-5,-7,6,-9,11,6,-14,-12,-10,9,-8,-7,5,6,8,-12,-1,-4,14,-3,0,7,9,7,12,13,-9,13,11,-10,-10,-9,-10,12,-10,8,-5,13,11,-8,7,-12,0,-11,2,-14,-8,8,-3,13,-9,5,5,7,-11,-6,5,-13,-7,1,14,-10,-1,-11,-13,4,12,-11,2,0,-4,-14,4,4,-10,13,-3,-10,6,1,-12,4,-9,1,-4,-13,10,8,-11,10,-14,-12,-14,1,-8,10,-10,11,-15,0,-3,-12,1,-14,-1,-1,6,11,-4,-3,-2,-1,-13 };
    vector<vector<int>> sum34 = s.threeSum(test2);
    print2d(sum34);

    // solution verification for test2
        //vector<vector<int>> solution = { { -15, 1, 14 },{ -15, 2, 13 },{ -15, 4, 11 },{ -15, 5, 10 },{ -15, 6, 9 },{ -15, 7, 8 },{ -14, 0, 14 },{ -14, 1, 13 },{ -14, 2, 12 },{ -14, 4, 10 },{ -14, 5, 9 },{ -14, 6, 8 },{ -14, 7, 7 },{ -13, -1, 14 },{ -13, 0, 13 },{ -13, 1, 12 },{ -13, 2, 11 },{ -13, 4, 9 },{ -13, 5, 8 },{ -13, 6, 7 },{ -12, -2, 14 },{ -12, -1, 13 },{ -12, 0, 12 },{ -12, 1, 11 },{ -12, 2, 10 },{ -12, 4, 8 },{ -12, 5, 7 },{ -12, 6, 6 },{ -11, -3, 14 },{ -11, -2, 13 },{ -11, -1, 12 },{ -11, 0, 11 },{ -11, 1, 10 },{ -11, 2, 9 },{ -11, 4, 7 },{ -11, 5, 6 },{ -10, -4, 14 },{ -10, -3, 13 },{ -10, -2, 12 },{ -10, -1, 11 },{ -10, 0, 10 },{ -10, 1, 9 },{ -10, 2, 8 },{ -10, 4, 6 },{ -10, 5, 5 },{ -9, -5, 14 },{ -9, -4, 13 },{ -9, -3, 12 },{ -9, -2, 11 },{ -9, -1, 10 },{ -9, 0, 9 },{ -9, 1, 8 },{ -9, 2, 7 },{ -9, 4, 5 },{ -8, -6, 14 },{ -8, -5, 13 },{ -8, -4, 12 },{ -8, -3, 11 },{ -8, -2, 10 },{ -8, -1, 9 },{ -8, 0, 8 },{ -8, 1, 7 },{ -8, 2, 6 },{ -8, 4, 4 },{ -7, -7, 14 },{ -7, -6, 13 },{ -7, -5, 12 },{ -7, -4, 11 },{ -7, -3, 10 },{ -7, -2, 9 },{ -7, -1, 8 },{ -7, 0, 7 },{ -7, 1, 6 },{ -7, 2, 5 },{ -6, -5, 11 },{ -6, -4, 10 },{ -6, -3, 9 },{ -6, -2, 8 },{ -6, -1, 7 },{ -6, 0, 6 },{ -6, 1, 5 },{ -6, 2, 4 },{ -5, -5, 10 },{ -5, -4, 9 },{ -5, -3, 8 },{ -5, -2, 7 },{ -5, -1, 6 },{ -5, 0, 5 },{ -5, 1, 4 },{ -4, -4, 8 },{ -4, -3, 7 },{ -4, -2, 6 },{ -4, -1, 5 },{ -4, 0, 4 },{ -4, 2, 2 },{ -3, -3, 6 },{ -3, -2, 5 },{ -3, -1, 4 },{ -3, 1, 2 },{ -2, 0, 2 },{ -2, 1, 1 },{ -1, -1, 2 },{ -1, 0, 1 },{ 0, 0, 0 } };
    //print2d(solution);
}

Attempt 4: O(n^2), TLE

I was pretty confident that I got this round, but all the extra processing that goes into converting for a set of tuples to a list, adds come constant time to the complexity.

The idea goes as follows. In the first approach, we iterated through pairs of i, j and k, where i=0, j=i+1, and k=j+1. The idea here is the same, except that we iterate though unique combinations of i, j, and use 2 sum to find valid k elements and will make numbers of i and j sum to 0. To do this, we hash every number in the array as a key to a list of unique indices. This way, when we find more than one possible target in the array, we can iterate though all valid solutions and append them to our array. The key here is that just like i, j, and k were all unique in the brute force solution, we can check for all i, j, k indices here as a set to have a length of 3 in order to indicate that they are unique as well. Additionally, if we do find a valid set, in order to avoid provided solutions that already exist, we store the sorted tuple into a set. This way, the set datastructure can identify unique sets.

from collections import defaultdict

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        sol = set()
        num_i = defaultdict(list)
        for i in range(0, len(nums)):
            num_i[nums[i]].append(i)

        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                # a + b + c = 0
                # c = -a + -b
                target = -nums[i] + -nums[j]
                for k in num_i[target]:
                    if len({i, j, k}) == 3:
                        sol.add(tuple(sorted([nums[i], nums[j], nums[k]])))

        return [[tup[0], tup[1], tup[2]] for tup in sol]


obj = Solution()
print(obj.threeSum([-1, 0, 1, 2, -1, -4]))