Algorithms to Find the Three Numbers in Array that Sum up to Zero (3Sum)


Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

The tricky bit is to deal with the duplicated triplets. We could use a hash set to avoid the duplicate triplets.

Bruteforce Algorithm to Search For Every Possible triplets O(N^3)

We can first sort the numbers, and bruteforce each possible triplets in O(N^3) time. As the numbers are searched in ascending order, we might be able to skip the duplicates for the first number. We can use the first two numbers as the keys for the hash set. The third number will be determined if the first two are set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        unordered_set<string> v;
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue; // the first number should be different
            for (int j = i + 1; j < nums.size(); ++ j) {
                for (int k = j + 1; k < nums.size(); ++ k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]);
                        if (!v.count(a)) {
                            r.push_back({nums[i], nums[j], nums[k]});
                            v.insert(a);
                        }
                    }
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        unordered_set<string> v;
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue; // the first number should be different
            for (int j = i + 1; j < nums.size(); ++ j) {
                for (int k = j + 1; k < nums.size(); ++ k) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]);
                        if (!v.count(a)) {
                            r.push_back({nums[i], nums[j], nums[k]});
                            v.insert(a);
                        }
                    }
                }
            }
        }
        return r;
    }
};

The space complexity is O(N) as we need to use a hash set.

Store the third number in hash map – Bruteforce Search Algorithm in O(N^2)

We can preprocess the numbers and store their max/last index in a hash map. Therefore, when we bruteforce the first two numbers in the triplets in O(N^2), we can locate (if any) the third number. If the index in the hash map is larger than the first two numbers’ indices, we find a match, but still need to use the hash set to avoid the duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        unordered_set<string> v;
        unordered_map<int, int> index;
        for (int i = 0; i < nums.size(); ++ i) {
            index[nums[i]] = { i };
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            for (int j = i + 1; j < nums.size(); ++ j) {
                int t = -(nums[i] + nums[j]);
                if (index.find(t) != index.end()) {
                    if (index[t] > j) {
                        string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]);
                        if (!v.count(a)) {
                            r.push_back({nums[i], nums[j], t});
                            v.insert(a);
                        }
                    }
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        unordered_set<string> v;
        unordered_map<int, int> index;
        for (int i = 0; i < nums.size(); ++ i) {
            index[nums[i]] = { i };
        }
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            for (int j = i + 1; j < nums.size(); ++ j) {
                int t = -(nums[i] + nums[j]);
                if (index.find(t) != index.end()) {
                    if (index[t] > j) {
                        string a = std::to_string(nums[i]) + "," + std::to_string(nums[j]);
                        if (!v.count(a)) {
                            r.push_back({nums[i], nums[j], t});
                            v.insert(a);
                        }
                    }
                }
            }
        }
        return r;
    }
};

The space complexity is O(N), as we need a hash set and a hash map.

Two Pointer Algorithm in O(N^2)

As the numbers are sorted, if we use O(N) to determine the first number, then in the sub-array, we can use two pointer algorithm to locate the second the third number with O(N). Overall, the two pointer algorithm as implemented in below C++ runs at O(N^2) complexiy – however, it is practically faster than the above O(N^2) solution – as we do not require a hash set to avoid duplicates, rather, we can just move forward the pointers if the sum stays the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            int j = i + 1;
            int k = nums.size() - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    r.push_back({nums[i], nums[j], nums[k]});
                    while ((j < k) && nums[j] == nums[j + 1]) j ++; // skip duplicates
                    while ((j < k) && nums[k] == nums[k - 1]) k --; // skip duplicates
                    j ++;
                    k --;
                } else if (nums[i] + nums[j] + nums[k] > 0) {
                    k --;
                } else {
                    j ++;
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> r;
        for (int i = 0; i < nums.size(); ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            int j = i + 1;
            int k = nums.size() - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    r.push_back({nums[i], nums[j], nums[k]});
                    while ((j < k) && nums[j] == nums[j + 1]) j ++; // skip duplicates
                    while ((j < k) && nums[k] == nums[k - 1]) k --; // skip duplicates
                    j ++;
                    k --;
                } else if (nums[i] + nums[j] + nums[k] > 0) {
                    k --;
                } else {
                    j ++;
                }
            }
        }
        return r;
    }
};

The Two Pointer implementation uses O(1) constant space.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
807 words
Last Post: How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)?
Next Post: WordPress Membership Plugin

The Permanent URL is: Algorithms to Find the Three Numbers in Array that Sum up to Zero (3Sum)

4 Comments

  1. Alberto
  2. hsinche

Leave a Reply