Extract one number from each array so that sum of numbers is 0?

Question

I am preparing for my Campus Placements. I came across a question, which goes like this:

Given 3 arrays, like

array 1: {2,1,4,7}
array 2: {3,-3,-8,0}
array 3: {-1,-4,-7,6}

We have to extract one number from each array and form triplets such that the sum of the numbers in the triplet is 0, or any number for that fact.

For example, for the above case, one of the solutions can be {2, -8, 6}

Currently, I have not been able to think of any solution other than the Brute Force method which will take O(n^3) time. How to do this in lesser time?

Thanks in advance.

@mamdouhalramadan what examples? he wants an algorithm. I myself am not interested in his bruteforce example ;) — lukas.pukenis, Sep 30 '13 at 12:54
@lukas.pukenis - I really didn't understand the purpose of this question :) sometimes I need an example to function :D — mamdouh alramadan, Sep 30 '13 at 12:56
I have edited the question to include one of the possible solutions. Also, i have not written any code because i know that Brute Force won't take me anywhere :) — R4chi7, Sep 30 '13 at 12:56

score 7 · Answer 1 · answered Sep 30 '13 at 12:57

7

A very simple solution is as follows:

Given a target T

Sort the third array
For each number N1 in the first array
- For each number N2 in the second array
  - Binary search the third array for (T - N1 - N2)

Running time = O(n^2 log n)

For the third array, you can also use a hash table, giving you an expected complexity of O(1) per lookup, thus O(n^2) in total, but I always feel that that's cheating a bit, as you depend on the set being well-distributed.

answered Sep 30 '13 at 12:57

Bernhard Barker

54,589
14
104
138

this is better than the brute force one, is it possible to improve it further or is this as far as it goes? – R4chi7 Sep 30 '13 at 12:58
1

Instead of sorting the third array, you could create a set from it. Checking set membership is [O(1) on average](https://wiki.python.org/moin/TimeComplexity), for a total complexity of O(n^2). – Kevin Sep 30 '13 at 12:59
@Kevin assuming you use a set implemented using hash not some self-balancing search tree. – Ivaylo Strandjev Sep 30 '13 at 13:00

score 6 · Answer 2 · answered Sep 30 '13 at 13:16

The problem is strongly related to the 3SUM problem. In fact, the 3SUM problem can be reduced to the problem you've stated (three arrays filled with the same n elements), so the problem is 3SUM-hard.

A faster than O(n^2) solution is hence highly unlikely, since this would contradict the conjectured quadratic time lower bound for the 3SUM problem.

score 2 · Accepted Answer · edited May 23 '17 at 11:57

You can do it in O(n^2):

Sort the second array into ascending order
Sort the third array into descending order
Loop through the first array.

Increment index of second or third array depending on whether the sum is negative or positive.

// Asssume array2 and array3 are sorted as mentioned above
// array2: {-8,-3,0,3}
// array3: {6,-1,-4,-7}
foreach (e1 in array1)
{
    int i2 = 0;
    int i3 = 0;
    while (i2 < array2.Length && i3 < array3.Length)
    {
        int sum = e1 + array2[i2] + array3[i3];
        if (sum == 0) Console.WriteLine( e1, array2[i2], array3[i3]);
        if (sum < 0) ++i2 else ++i3;
    }

}

related: Finding three elements in an array whose sum is closest to a given number

umm..can you post some pseudocode? that would be really helpful :) — R4chi7, Sep 30 '13 at 13:05

score 1 · Answer 4 · answered Sep 30 '13 at 12:58

You can reduce complexity to O(log(N) * N^2) if you sort one array and perform binary search for the negation of the sum of any pair of elements from the other two arrays.

If the range of the values of the numbers in the arrays is relatively small you can improve this further by using a counting sort algorithm or some other linear non-comparison sort algorithm.

Another improvement would be to use a hashset for the numbers of the first array thus getting a complexity of O(N^2) as proposed by Kevin.

Extract one number from each array so that sum of numbers is 0?

4 Answers4