## Finding all unique triplets that sums to zero

April 12, 2010

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

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

One possible solution set is:
(-1, 0, 1)
(-1, 2, -1)

Note that (0, 1, -1) is not part of the solution above, because (0, 1, -1) is the duplicate of (-1, 0, 1). Same with (-1, -1, 2).

For a set S, there is probably no “the” solution, another solution could be:
(0, 1, -1)
(2, -1, -1)

Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++/Java code. If you are using other languages, you can still verify your solution by looking at the judge’s test cases and its expected output.

This is also known as the 3sum problem. The 3sum problem is the extension of the problem below:

Given a set S of n integers, find all pairs of integers of a and b in S such that a + b = k?

The above problem can be solved in O(n) time, assuming that the set S is already sorted. By using two index first and last, each pointing to the first and last element, we look at the element pointed by first, which we call A. We know that we need to find B = k – A, the complement of A. If the element pointed by last is less than B, we know that the choice is to increment pointer first by one step. Similarly, if the element pointed by last is greater than B, we decrement pointer last by one step. We are progressively refining the sum step by step. Since each step we move a pointer one step, there are at most n steps, which gives the complexity of O(n).

By incorporating the solution above, we can solve the 3sum problem in O(n^2) time, which is a straight forward extension.

Note that a set is chosen to store the triplets, because we are only interested in unique triplets. Since the set S is already sorted, and we don’t look back as it progresses forward, we can guarantee there will be no duplicate triplets (Even though the set might have duplicate elements.)

Further Thoughts:
Now, a challenge for you. Could you figure out a way to compute your solution set with only unique triplets without the help of a build-in data structure (such as set<>)?

VN:F [1.9.22_1171]
Finding all unique triplets that sums to zero, 3.9 out of 5 based on 11 ratings

### 46 responses to Finding all unique triplets that sums to zero

1. Hi,

The two problems you have stated are not same. For the problem "Given a set S of n integers, find all pairs of integers of a and b in S such that a + b = k?", k need not be from the set S and can be any integer, while in the problem "Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?", all a, b and c are from the set S.

VA:F [1.9.22_1171]
0
2. So? if you can solve for any integer k, why can't it apply to -c?

VA:F [1.9.22_1171]
+1
3. In a+b+c=0 problem, we have to repeat the above logic for ever 'c' in the array. Eg: take element a[10], search from 1 to 9 to see if we get a+b=-c. Total running time will be O(n^2)

VA:F [1.9.22_1171]
0
4. Hi,
I think you solution can not guarantee the uniqueness of the triplets. For example, if the original sorted set is {-1,-1,-1,0,2,2}, you'll pick the solution (-1,-1,2) twice, {i=0,j=1,k=5} and {i=1,j=2,k=4}. So before you do triplets.insert(triplet), you need to check if the triplet is already in the triplets. Correct me if I am wrong.

VA:F [1.9.22_1171]
0
5. Sorry, one typo in the above post, should be {i=0,j=1,k=5} and {i=0,j=2,k=4}

VA:F [1.9.22_1171]
0
6. The uniqueness is guaranteed not by the algorithm itself, but by using map in C++, which does not allow duplicate elements in it. Since the list is sorted, duplicated elements will also be sorted.

VA:F [1.9.22_1171]
0
7. Have you heard of binomial coefficients?

Let’s say the set is size 6. We want all possible permutations of size 3. Then we evaluate all of these to see if they add up to 0.

6 choose 3 = 6!/(3!*(6-3)!)
This comes out to 20 different combinations.

We just iterate through these 20 combinations to add up the values and see if they resolve to 0.

20 iterations is a lot less then 36….unless you can prove that the amortized cost of your algorithm is less then n^2.

VA:F [1.9.22_1171]
0
• JJ said on March 7, 2011

Well .. that’s the whole point of asymptotic complexity. It is not whether a particular solution is better for some value of ‘n’, but whether it gets better as n grows larger and larger.

In your case, consider a set of size 10 (n=10). Now you need 10 choose 3, i.e. 120 combinations, whereas n^2 would be 100.

What if n = 100? Enumerating all combinations would essentially be O(n^3), whereas the approach mentioned here is only O(n^2)

VA:F [1.9.22_1171]
+1
• This is the code:

public class UniqueTriplets {
public static void find(int[] ary, int[] out, int level, int start) {
for(int i=start; i<ary.length; i++) {
out[level] = ary[i];
if(level == 2) {
if(out[0]+out[1]+out[2]==0)
System.out.println(out[0]+" "+out[1]+" "+out[2]);
} else if(level < 2) {
find(ary, out, level+1, i+1);
}
}
}

/**
* @param args
*/
public static void main(String[] args) {
int[] ary = {-1, 0, 1, 2, -1, -4};
int[] out = new int[3];
find(ary, out, 0, 0);

}
}

VA:F [1.9.22_1171]
0
8. Not sure about two things.

1. Is the declaration “vector triplet(3)” a typo? Should it be “vector triplet[3]“?

2. In a set, would vector(-1, 0, 1) and vector(0, 1, -1) be deemed the same element, or different elements? A set is a sorted data structure, but what is the sorting criterion for a set whose elements are vectors? How can the vectors be compared to each other? Shouldn’t vector(-1, 0, 1) and vector(0, 1, -1) be treated as two different vectors? If they are two different vectors, then the set data structure can’t garantee the uniqueness of the combination.

Confused…

VA:F [1.9.22_1171]
0
9. Sorry, just got to understand the statement “vector triplet(3)”. tripet(3) is a constructor with the size 3 as an argument.

Still, my confusion about how the vectors compare with each other remains…

VA:F [1.9.22_1171]
0
• The input has been sorted, so you will not get {-1, 0, -1} as an triplet. The only way for a triplet is {smallest, second_smallest_or_equal_to_smallest, third_smallest_or_equal_to_second_smalllest}

VA:F [1.9.22_1171]
0
10. why cant we find out (0 – sum2) in the array starting at j + 1 using binary search? complexity will be N(logN)

static Set<List> sum3Better(int[] a, int sum) {
Set<List> retval = new HashSet<List>();
for(int i = 0; i = 0) {
List triplet = new ArrayList();
}
}
return retval;
}

VA:F [1.9.22_1171]
0
• Didn’t see your binary search in code. I am not sure if I understand your idea correctly, it looks to me that you are doing something like this,

Loop through the array from 0 to (size-1) for the outside loop, O(N)
Then a second loop starting from (i+1) to (size-1)? O(N)
Then do binary search for the target value of (sum-array(i)-array(i+1)), which gives you log(n).

Total complexity would be N*N*log(N)?

VA:F [1.9.22_1171]
0
• Sorry about messed up code posting above.

The idea is
1. Loop through the array from 0 to (size-2) for the outside loop, O(N), pointer i

2.
pointer j = i + 1
sum2 = data[i] + data[j]
key = 0 – sum2;

3.
pointer k = find(data, j + 1, data.length, key);, O(logN)
if(k != -1) {
// found 1 solution data[i], data[j] and data[k]
}

Therefore, Nlog(N)

VA:F [1.9.22_1171]
0
11. @1337c0d3r :
How ur code for
Given a set S of n integers, find all pairs of integers of a and b in S such that a + b = k?

has complexity 0(n) ?
there are two loops?
comlexity should be o(n^2)
can anybody explain ?

VN:F [1.9.22_1171]
0
12. yes,it could be done without the help of a set like data structure. While traversing(either from left or right), if an element is equal to last element that you traversed , ignore it and move to next index.

VA:F [1.9.22_1171]
0
13. by “last element that you traversed” i mean last element that you traversed through or encountered while traversing.

VA:F [1.9.22_1171]
0
• doesn’t work in this case [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6], where you have 3 “-2″, and you will get [-2 -2 4] [-2 0 2] [-2 -2 4] [-2 0 2]. So you need to remove any number repeating for more than 2 times in the array.

VN:F [1.9.22_1171]
0
• here we come to this scenario that num[i]+num[j]+num[k] = 0 and we’ve to update the j,k to find if there’re other pairs exists for current i.
when j needs to update you’ve to check if(num[j+1] == num[j]) if so skip it and compare with the next valueï¼Œhere you may need a variable to count how many num[j] are exist in the array and then update the j with this count value j+= count;
the same thing needs to do when i and k are needs to update their value.

VN:F [1.9.22_1171]
0
14. et said on June 1, 2012

Hi there,
Where can I see the test case and output result?

Thanks,

VA:F [1.9.22_1171]
0
15. If sorting is not allowed can we have better solution than o(n^3)?

VA:F [1.9.22_1171]
0
16. VN:F [1.9.22_1171]
0
• Sorry, please ignore the “img” label on line 26, this sentence should be

VN:F [1.9.22_1171]
0
• the increment sentence of this for is empty, and the condition sentence of this for is “j < k"

VN:F [1.9.22_1171]
0
17. I need to know if there is a better approach when we are not allowed to change the input dataset ( like sorting the num parameter, Copying is also not allowed, memory may not be avalilable!)

Is brute force the only way, or can we use any cheap tricks that use a limited ( constant amount of memory ( say k units when k <<< num.size() )

VA:F [1.9.22_1171]
0
18. VN:F [1.9.22_1171]
0
19. For determining if 2 numbers add to a target sum, is it necessary to progress the indexes linearly? Can it be done in a binary search fashion?

VA:F [1.9.22_1171]
0
20. I am also thinking about the binary search, it seems the complexity can be O(NlogN). can anyone point out where is wrong ? :
After sorting, we have two index first = 0, last = n-1. keep a[first], a[last] as candidates, and binary search k – a[first] – a[last] in a[first, last], and keep updating first or last at one time.

pesudo code :
iterCount = 0
while first <= last
// binary search, test k – a[first] – a[last] in a[first, last]
// if in , add triplet

if iterCount odd, first++
else last–
iterCount++
end while

Obviously, the outer loop iterCount is O(N), the binary search is O(logN)

VN:F [1.9.22_1171]
0
• What is the reason of checking iterCount is odd/even?
Think your algorithm may not work for the test case below:

[-5, 0, 2, 3, 4, 6]

It seems you never get a chance to check the triple [-5, 2, 3]

VN:F [1.9.22_1171]
0
21. My program below passes for “Judge Small” but throws Timeout Exceeded for “Judge Large”. Any pointer/advice on how to overcome this issue?

VN:F [1.9.22_1171]
0
22. The sample code in the blog can already guarantee that the second and third num will not repeat. To compute unique triplet without set, it just need to check in the outer loop that if arr[i] equals to arr[i-1]. The inner loop can be skipped if they are equal.

VN:F [1.9.22_1171]
0
• Modified: there’s still chance last two numbers are identical, so it may also check for j and k to make sure arr[j] != arr[j-1] and arr[k] != arr[k+1]. Following is the tested Java Code:

public ArrayList<ArrayList> threeSum(int[] num) {
ArrayList<ArrayList> result = new ArrayList<ArrayList>();

if (num == null || num.length < 3)
return result;

Arrays.sort(num);

int n = num.length;
for (int i = 0; i < n; ++i) {
if (i == 0 || num[i] != num[i - 1]) {
int j = i + 1;
int k = n – 1;

while (j < k) {
int sum = num[i] + num[j] + num[k];
if (sum < 0)
while (++j 0)
while (j < –k && num[k] == num[k + 1]);
else {
ArrayList triple = new ArrayList(3);
while (++j < k && num[j] == num[j - 1]);
while (j < –k && num[k] == num[k + 1]);
}
}
}
}

return result;
}

VN:F [1.9.22_1171]
0
• Modified: there’s still chance last two numbers are identical, so it may also check for j and k to make sure arr[j] != arr[j-1] and arr[k] != arr[k+1]. Following is the tested Java Code:

public ArrayList<ArrayList> threeSum(int[] num) {
ArrayList<ArrayList> result = new ArrayList<ArrayList>();

if (num == null || num.length < 3)
return result;

Arrays.sort(num);

int n = num.length;
for (int i = 0; i < n; ++i) {
if (i == 0 || num[i] != num[i - 1]) {
int j = i + 1;
int k = n – 1;

while (j < k) {
int sum = num[i] + num[j] + num[k];
if (sum < 0)
while (++j 0)
while (j < –k && num[k] == num[k + 1]);
else {
ArrayList triple = new ArrayList(3);
while (++j < k && num[j] == num[j - 1]);
while (j < –k && num[k] == num[k + 1]);
}
}
}
}

return result;
}

Large Test runs 711ms on my machine.

VN:F [1.9.22_1171]
0
23. Here’s my solution in java:

VA:F [1.9.22_1171]
0
24. Your home is valueble for me. Thanks!…

VA:F [1.9.22_1171]
0
25. following is the algorithm for finding all the triplets that sum to T (i.e.passing 0 result in the required algorithm). Runtime complexity is O(n2).

VN:F [1.9.22_1171]
0
• I am sorry few mistakes are present in the above code. following is the correct code.
1. end should always start form n-1.
2. comparision in nested loop should be < not <= to avoid duplicate.

VN:F [1.9.22_1171]
0
26. a doubt: std::set::insert also takes O(logN), so how can your code be O(n-square) ?

VA:F [1.9.22_1171]
0
27. this is absolutely one O(n^3) problem. Imagine all number is 0, there are choose (n,3) possibilities …

VA:F [1.9.22_1171]
+1