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.

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 |
set<vector<int> > find_triplets(vector<int> arr) { sort(arr.begin(), arr.end()); set<vector<int> > triplets; vector<int> triplet(3); int n = arr.size(); for (int i = 0;i < n; i++) { int j = i + 1; int k = n - 1; while (j < k) { int sum_two = arr[i] + arr[j]; if (sum_two + arr[k] < 0) { j++; } else if (sum_two + arr[k] > 0) { k--; } else { triplet[0] = arr[i]; triplet[1] = arr[j]; triplet[2] = arr[k]; triplets.insert(triplet); j++; k--; } } } return triplets; } |

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<>)?

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.

+2So? if you can solve for any integer k, why can't it apply to -c?

+1In 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)

+2Hi,

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.

0i think set stores unique items

+2i agree, maybe the people who give -1 can help to explain.

+1Sorry, one typo in the above post, should be {i=0,j=1,k=5} and {i=0,j=2,k=4}

0The 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.

-1Have 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.

0Well .. 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)

+4This 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);

}

}

0Not 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…

+2Sorry, 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…

0The 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}

0why 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();

triplet.add(a[i]);

triplet.add(a[j]);

triplet.add(a[index]);

retval.add(triplet);

}

}

return retval;

}

0Didn’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)?

+1Sorry 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)

0wrong.

0@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 ?

0try doing some homework .

-1yes,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.

-1by “last element that you traversed” i mean last element that you traversed through or encountered while traversing.

-1doesn’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.

+1here 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.

0Hi there,

Where can I see the test case and output result?

Thanks,

0http://www.leetcode.com/onlinejudge

0If sorting is not allowed can we have better solution than o(n^3)?

00Sorry, please ignore the “img” label on line 26, this sentence should be

0the increment sentence of this for is empty, and the condition sentence of this for is “j < k"

0this is really a good solution to get the unique triple.

0I 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() )

00For 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?

0I 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)

0What 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]

0My program below passes for “Judge Small” but throws Timeout Exceeded for “Judge Large”. Any pointer/advice on how to overcome this issue?

0time limit exceeded**

0The 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.

0Modified: 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);

triple.add(num[i]);

triple.add(num[j]);

triple.add(num[k]);

result.add(triple);

while (++j < k && num[j] == num[j – 1]);

while (j < –k && num[k] == num[k + 1]);

}

}

}

}

return result;

}

0Modified: 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);

triple.add(num[i]);

triple.add(num[j]);

triple.add(num[k]);

result.add(triple);

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.

0Pingback: Idea Board Finding all unique triplets that sums to zero | Idea Board

Here’s my solution in java:

0Your home is valueble for me. Thanks!…

0following 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).

0I 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.

0a doubt: std::set::insert also takes O(logN), so how can your code be O(n-square) ?

0this is absolutely one O(n^3) problem. Imagine all number is 0, there are choose (n,3) possibilities …

+1Pingback: Finding all unique triplets that sums to zero - JavaScript - GeniusCarrier

@pploo and @Chun Zhang, Hi, there is indeed O(N^2) solutions, it is just the one here using std::set which involves balanced binary search tree accidently cannot achive this, I have posted sourcecode of 3sum and more general discussion on K sum problems here, http://tech-wonderland.net/blog/summary-of-ksum-problems.html you might want to check this out for any further references.

0Your online judge doesn’t accept hash_map and hash_set in c++?

0Hi.

Are {-1, 0, 1} and {-1, 0, 1} consider duplicate?(The -1’s are different ones)

+1how to find unique triplets without using sets in c++? can anybody please help me here??

0check the response posted by yunitst on November 29, 2012, it might be helpful.

0Pingback: Q015 3Sum | ardpx69

Pingback: Interview - Jung's Wiki

0The comment system swallows some > and < signs, the above code is displayed incorrectly.

Here is the correctly displayed code: http://ideone.com/y3We75

0