Finding all unique triplets that sums to zero (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. (i.e., a \leq b \leq c)
  • The solution set must not contain duplicate triplets.

INPUT: S = {-1, 0, 1, 2, -1, -4}
OUTPUT: (-1, 0, 1) and (-1, -1, 2)

Thoughts:
Apparently a O(n^{3}) algorithm exists but we can ignore it. To do better than that, we notice that if we can afford O(n^{3}), we can first sort S in O(n\log n). Does sorting help us in any way? The answer is definitely yes because it points out the direction of search for us. We can have a O(n^{2}) algorithm:
At outer loop, we iterate through every position from 0 to n-1. For a particular position i, we look at all the element between S[i+1] to S[n-1] (remeber that they are all sorted). We initialize two pointers j = i+1 and k = n-1. In the inner loop, we compute the sum s = a[i]+ a[j]+ a[k]. If s is bigger than 0, then we know we need to find something smaller, we decrease k. If s is smaller than 0, then we know we need to find something bigger, so we increase j. If the sum is exactly 0, we mark the triplet down and put it into the solution set (in order to find all of the solutions, we need to decrease k and increase j at the same time for this case). We continue this process until j exceeds k. Therefore, the worst case for inner loop is to look at everything between S[i+1] to S[n-1]. But each time we increase i by 1 at outer loop, we have 1 less element needed to look at inner loop. Explicitly, the overall running time is given by (n-1) + (n-2) + ... + 1 \equiv O(n^{2}).

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = 
                new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for(int i = 0; i < num.length; ++i) {
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) {
                int sum = num[i] + num[j] + num[k];
                if(sum == 0) {
                    ArrayList<Integer> triplet = 
                            new ArrayList<Integer>();
                    triplet.add(num[i]);
                    triplet.add(num[j]);
                    triplet.add(num[k]);
                    if(!result.contains(triplet))
                        result.add(triplet);
                    j++;
                    k--;
                } else if(sum > 0) {
                    k--;
                } else { // sum < 0
                    j++;
                }
            }
        }
        return result;
    }
}

Code (C++):

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > solution;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size(); ++i) {
            int j = i + 1;
            int k = num.size() - 1;
            while (j < k) {
                int sum = num[i] + num[j] + num[k];
                if(sum == 0) {
                    vector<int> triplet(3);
                    triplet[0] = num[i];
                    triplet[1] = num[j];
                    triplet[2] = num[k];
                    if(find(solution.begin(), solution.end(),
                        triplet) == solution.end())
                        solution.push_back(triplet);
                    j++;
                    k--;
                } else if(sum > 0) {
                    k--;
                } else { // sum < 0
                    j++;
                }
            }
        }
        return solution;
    }
};
Advertisements

2 Comments (+add yours?)

  1. Trackback: Finding sum of triplets that is closest to a given number (3sum closest) « Runhe Tian Coding Practice
  2. Trackback: Finding all unique quadruplets that sums to zero (4 sum) « Runhe Tian Coding Practice

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: