Finding all unique triplets that sums to zero

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]
Rating: 4.1/5 (34 votes cast)
Finding all unique triplets that sums to zero, 4.1 out of 5 based on 34 ratings

58 thoughts on “Finding all unique triplets that sums to zero

  1. Prateek

    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]
    +2
  2. Anonymous

    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]
    +2
  3. Anonymous

    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
  4. Tracy

    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]
    -1
  5. Kay

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

      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]
      +4
    2. opoopo

      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
  6. johny

    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]
    +2
  7. johny

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

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

      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]
      +1
      1. dilbert

        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
  8. shirdisai

    @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
  9. Eric-Draven

    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]
    -1
  10. Eric-Draven

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

    VA:F [1.9.22_1171]
    -1
    1. kenneth

      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]
      +1
      1. chris

        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
  11. Chenguang Yang

    VN:F [1.9.22_1171]
    0
  12. Srikanth

    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
  13. Jill

    VN:F [1.9.22_1171]
    0
  14. Dchang

    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
  15. zy

    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
  16. Arham

    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
  17. yunitst

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

      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);
      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;
      }

      VN:F [1.9.22_1171]
      0
    2. yunitst

      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);
      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.

      VN:F [1.9.22_1171]
      0
  18. Pingback: Idea Board Finding all unique triplets that sums to zero | Idea Board

  19. Ozan Tabak

    Here’s my solution in java:

    VA:F [1.9.22_1171]
    0
  20. Laiq Ahmed

    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
    1. Laiq Ahmed

      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
  21. Pingback: Finding all unique triplets that sums to zero - JavaScript - GeniusCarrier

  22. Pingback: Q015 3Sum | ardpx69

  23. Pingback: Interview - Jung's Wiki

  24. madno

    VN:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*