1

I've got all unique triplets from code below but I want to reduce its time complexity. It consists of three for loops. So my question is: Is it possible to do in minimum number of loops that it decreases its time complexity?

Thanks in advance. Let me know.

   #include <cstdlib>
    #include<iostream>
    using namespace std;
    void Triplet(int[], int, int); 
    void Triplet(int array[], int n, int sum)
    {
       // Fix the first element and find other two
         for (int i = 0; i < n-2; i++)
         {
            // Fix the second element and find one
               for (int j = i+1; j < n-1; j++)
            {
               // Fix the third element
               for (int k = j+1; k < n; k++)
               if (array[i] + array[j] + array[k] == sum)
                cout << "Result :\t" << array[i] << " + " << array[j] << " + " << array[k]<<" = " << sum << endl;
             }
          }
     }

    int main()
    {
        int A[] = {-10,-20,30,-5,25,15,-2,12};
        int sum = 0;
        int arr_size = sizeof(A)/sizeof(A[0]);
        cout<<"********************O(N^3) Time Complexity*****************************"<<endl;
        Triplet(A,arr_size,sum);
        return 0;
    }
LogicStuff
  • 19,397
  • 6
  • 54
  • 74
Paddy
  • 13
  • 1
  • 10
  • Disregarding the "unique" requirement, the number of triplets that can sum to zero is quadratic in the length of the array. So I don't think you can do better than quadratic. However, it's trivial to do quadratic. – Cheers and hth. - Alf Feb 28 '15 at 11:34
  • The question [Finding three elements that sum to K](http://stackoverflow.com/questions/28128082/finding-three-elements-that-sum-to-k) deals with finding triplets in a set. This question deals with finding triplets in an array. The difference demands for a different algorithm. I vote to reopen. – Oswald Feb 28 '15 at 16:54

4 Answers4

1

I'm not a wiz at algorithms but a way I can see making your program better is to do a binary search on your third loop for the value that will give you your sum in conjunction with the 2 previous values. This however requires your data to be sorted beforehand to make it work properly (which obviously has some overhead depending on your sorting algorithm (std::sort has an average time complexity of O (n log n))) .

You can always if you want to make use of parallel programming and make your program run off multiple threads but this can get very messy.

Aside from those suggestions, it is hard to think of a better way.

Hayden
  • 2,902
  • 2
  • 15
  • 29
  • Dang, you beat me to it. :P – Alejandro Feb 28 '15 at 12:02
  • Instead of a simple `std::sort`, you can also combine that with something to remove duplicates. (See [here](http://stackoverflow.com/questions/1041620/whats-the-most-efficient-way-to-erase-duplicates-and-sort-a-vector), for instance.) Removing duplicates will make sure you only print unique triplets, without increasing the complexity of the function. –  Feb 28 '15 at 12:36
  • @hvd that would provide a solution to uniqueness, I was just providing a simple example however and didn't want to go into that much detail. – Hayden Feb 28 '15 at 12:43
  • Thanx to all of you.. my frds. Actually I've tried with sort but it will give only two triplets. – Paddy Mar 02 '15 at 03:35
  • @Paddy I strongly recommend looking at the duplicate question, it will give you a o (n^2) solution. – Hayden Mar 02 '15 at 05:35
  • Ok,hayden.. i ll try.. – Paddy Mar 02 '15 at 10:17
0

You can get a slightly better complexity of O(n^2*logn) easily enough if you first sort the list and then do a binary search for the third value. The sort takes O(nlogn) and the triplets search takes O(n^2) to ennumerate all the possible pairs that exist times O(logn) for the binary search of the thrid value for a total of O(nlogn + n^2logn) or simply O(n^2*logn).

There might be some other fancy things with binary search you can do to reduce that, but I can't see easily (at 4:00 am) anything better than that.

Alejandro
  • 1,168
  • 8
  • 11
0

When a triplet sums to zero, the third number is completely determined by the two first. Thus, you're only free to choose two of the numbers in each triple. With n possible numbers this yields maximum n2 triplets.

I suspect, but I'm not sure, that that's the best complexity you can do. It's not clear to me whether the number of sum-to-zero triplets, for a random sequence of signed integers, will necessarily be on the order of n2. If it's less (not likely, but if) then it might be possible to do better.

Anyway, a simple way to do this with complexity on the order of n2 is to first scan through the numbers, storing them in a data structure with constant time lookup (the C++ standard library provides such). Then scan through the array as your posted code does, except vary only on the first and second number of the triple. For the third number, look it up in the constant time look-up data structure already established: if it's there then you have a potential new triple, otherwise not.

For each zero-sum triple thus found, put it also in a constant time look-up structure.

This ensures the uniqueness criterion at no extra complexity.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331
  • I think you're thinking of `std::unordered_set` for the data structure with constant lookup time? It's worth pointing out that it's constant time on average, but not necessarily constant time for all inputs. But you were right nonetheless that there is an easy O(n^2) algorithm. I've closed the question as a duplicate of one that contains that has a decent answer with that algorithm. –  Feb 28 '15 at 12:55
  • Sorry for posting this perhaps too concrete answer to what appears to be a homework or competition question. But there was some heated commentary. – Cheers and hth. - Alf Feb 28 '15 at 12:55
  • To be clear, I didn't close the question as a duplicate because of your answer or comments, I closed the question as a duplicate because it's a duplicate. I merely happened to find that other question shortly after your answer. –  Feb 28 '15 at 13:00
-1

In the worst case, there are C(n, 3) triplets with sum zero in an array of size n. C(n, 3) is in Θ(n³), it takes Θ(n³) time just to print the triplets. In general, you cannot get better than cubic complexity.

Oswald
  • 31,254
  • 3
  • 43
  • 68
  • **–1** "you cannot get better than cubic complexity" is self-evidently false. – Cheers and hth. - Alf Feb 28 '15 at 12:08
  • 2
    "Nu-uh!" is not a valid argument. Anyway, to give a better reason that this answer isn't quite right, the question only asks for the unique triplets, and better answers have already been posted. The trivial case where every triplet has sum zero (every element itself is zero) has only one unique triplet, for instance. –  Feb 28 '15 at 12:14
  • I ignored "unique" because Paddy ignored it in his code. – Oswald Feb 28 '15 at 12:17