Finding complementary pairs

Question

I've read the docs online explaining Log N and I do understand that the basic concept of it, but I'm still not sure I've managed to nail it.

The problem

This exercise is called "Complementary Pairs" and given an array A and an integer K, how many pairs of A, sum to K.

For example, with this input:

k = 6 a = [1, 8, -3, 0, 1, 3, -2, 4, 5] 

we would have 7 possibilities, like i, j = (5, 5) to add 3 + 3, then the pairs that add 1 + 5 (and the reverse), etc.

Naive solution

A first very naive solution is to for a \$O(N^2)\$ complexity loop where you just bluntly search the array in two nested loops.

\$N * Log N\$ Solution

From my understanding a proper \$Log N\$ solution has to include a binary search like quicksort or mergesort, so I applied a divide and conquer algorithm where I split the array in two, until it's down to one element, then I assemble back again, and I for a \$N*N\$ search on array, checking which elements of the first added with the second add to constant K.

Although this is very similar to mergesort, it just doesn't feel a \$N * Log N\$ solution, because the worst case, the last recursion step, I'm doing \$N/2 * N/2\$ and for me that's just \$N*N\$ over time.

Here is the working solution:

var complementary_pairs = function (input, k) {
 // Base scenario
 if (input.length == 1) { 
 return input[0] * 2 == k ? 1 : 0
 }
 // Recursion
 var middle = Math.ceil(input.length / 2)
 , firstArray = input.slice(0, middle)
 , secondArray = input.slice(middle)
 var count = complementary_pairs(firstArray, k)
 + complementary_pairs(secondArray, k)
 // Problem condition
 for (var i = 0; i < firstArray.length; i++) {
 for (var j = 0; j < secondArray.length; j++) {
 if (firstArray[i] + secondArray[j] == k) {
 count += 2
 }
 }
 }
 return count
}
console.log(complementary_pairs([1, 8, -3, 0, 1, 3, -2, 4, 5], 6))

Answer 1

I might have missed something but I think I do have an O(n*log(n)) solution.

Assuming A is your array of size n and K is the integer.

• Sort A with a efficient sorting algorithm (mergesort, quicksort, etc) : this is O(n*log(n))

• For each element x in A:

  • Use binary search to find the first occurrence of K-x (if any) : this is O(log(n))

  • Use binary search to find the last occurrence if K-x (if any) : this is O(log(n))

    -> These steps allow you to find the number of instances of K-x in O(log(n))

  ->This allows you to count the number of pairs in O(n*log(n)). Each pair has been counted twice.

Many minimal optimisations could be performed :

• Handling the identical values of x in one go
• Looping could stop when 2*x > K
• Binary search could be limited to a smaller sub-array as we progress through A
• Etc

Please let me know if I missed something.

Edit : Here's a quick attempt with an initial array containing the original array twice to make testing somewhat easier.

I've included different versions, more and more optimised. One could go further but I started to have doubts about the correctness :-)

Corresponding jsfiddle

var a = [1, 8, -3, 0, 1, 3, -2, 4, 5, 1, 8, -3, 0, 1, 3, -2, 4, 5];
var target = 6;
a.sort(function(a, b) {return a - b});
function binarySearch(a, k, lastOcc, min)
{
 var min = (typeof(min)==='undefined') ? 0 : min
 var max = a.length-1
 while (min <= max)
 {
 var range = max-min
 var midf = min + (range / 2)
 var mid = lastOcc ? Math.ceil(midf) : Math.floor(midf)
 var x = a[mid]
 if (x < k) min = mid+1
 else if (x > k) max = mid-1
 else if (min==max) return mid
 else if (lastOcc) min = mid
 else max = mid
 }
 return -1
}
// Zeroth solution
var count = 0
for (var i=0; i<a.length; i++)
{
 for (var j=0; j<a.length; j++)
 {
 if (a[i]+a[j]==target) count++
 }
}
console.log(count)
// First solution
var count = 0
for (var i=0; i<a.length; i++)
{
 var v = a[i]
 var x = target-v
 var f = binarySearch(a,x,false)
 if (f>-1)
 {
 var l = binarySearch(a,x,true)
 var nb = 1+l-f
 count+=nb
 }
}
console.log(count)
// Second solution - skipping over identical values
var count = 0
for (var i=0; i<a.length; i++)
{
 var v = a[i]
 var coef = 1
 while (i+1<a.length && a[i+1]==v)
 {
 coef++
 i++
 }
 var x = target-v
 var f = binarySearch(a,x,false)
 if (f>-1)
 {
 var l = binarySearch(a,x,true)
 var nb = 1+l-f
 count+=nb*coef
 }
}
console.log(count)
// Third solution - stopping once enough is enough
var count = 0
for (var i=0; i<a.length; i++)
{
 var v = a[i]
 var coef = 1
 while (i+1<a.length && a[i+1]==v)
 {
 coef++
 i++
 }
 var x = target-v
 if (v <= x)
 {
 if (v != x) coef*=2
 var f = binarySearch(a,x,false)
 if (f>-1)
 {
 var l = binarySearch(a,x,true)
 var nb = 1+l-f
 count+=nb*coef
 }
 }
 else break
}
console.log(count)
// Fourth solution - limiting the binary search to a smaller scope
var count = 0
for (var i=0; i<a.length; i++)
{
 var oldi=i
 var v = a[i]
 var coef = 1
 while (i+1<a.length && a[i+1]==v)
 {
 coef++
 i++
 }
 var x = target-v
 if (v < x)
 {
 var f = binarySearch(a,x,false,i)
 if (f>-1)
 {
 var l = binarySearch(a,x,true,f)
 var nb = 1+l-f
 count+=2*nb*coef
 }
 }
 else if (x==v)
 {
 count+=coef*coef
 break
 }
 else break
}
console.log(count)

Re-edit :

I've tested my code with the following inputs and all functions are returning the same values... but not in the same time.

var a = []
for (var i=0; i<10000; i++)
{
 a.push(Math.floor(Math.random()*20))
}
var target = a[0]+a[1]; // ensuring results

Zeroth solution is O(n^2) First solution is O(n*log(n) + n*log(n)) which is O(n*log(n)) Second solution is stricly better. Third solution is stricly better. Fourth solution is stricly better.

• Vedran Šego: I think you don't need to Use binary search to find the last occurrence if K-x (if any). Just go from the first one, and lineary check how many of them are.
• bitoiu: I'm just missing what you mean by K-x. I though of sorting the array first, but I didn't see how could I traverse it with a O(n) complexity. I need to find all the pairs (x,x') where A[x] + A[x'] = k. Is that what you said?
• Vedran Šego: @bitoiu x is an element of a, not an index. ;-) So, if x = a[i] for some i, you're looking for K - x = K - a[i] in the array. If you find it, i.e., you find j such that a[j] = K - x = K - a[i], you've found a pair.
• SylvainD: @VedranŠego I wanted to avoid checking lineary how many of them we have. Just to be safe, I'd rather perform 2 logarithmic operations. (It's not only about me being paranoid, I was mostly looking for a proof of concept)
• SylvainD: @VedranŠego This being said, I now have doubts than binary search on first and last occurrences are actually. Let's implement this and see :-)

Answer 2

This is not O(n log n) algorithm, because this part is quadratic:

 for (var i = 0; i < firstArray.length; i++) {
 for (var j = 0; j < secondArray.length; j++) {
 if (firstArray[i] + secondArray[j] == k) {
 count += 2
 }
 }
 }

Denoting n = input.length, this has roughly (n/2)^2 = n^2/4 steps, which is O(n^2).

The rest of this answer is a result of a misread and is not directly related to the question. I'll leave it as a comment of a possibly extended exercise.

However, I'm not sure that O(n log n) algorithm does exist. Consider

a = [ 1, 2, 4, 8, ..., 2^n ] (for some n)

and k is a sum of all elements in a. Since you can repeat the numbers, and a[k] = 2*a[k-1] for all positive k, you'd have exponential number of sums, so no O(n log n) algorithm will solve this.

It is easy to show that the number of solutions is strictly bigger than 2^n. Just note that

k = (sum of ANY elements in a except a[0] = 1) + (sum of the remaining elements in a) * 1.

The first sum can be chosen in 2^n ways. Of course, there are other sums as well, but this is enough to show that you can have an exponential number of solutions, which is enough to show that no sub-exponential algorithm can find them all.

Of course, there may be a mathematical trick to compute only how many such solutions there are, but I don't know it.

• bitoiu: thanks for a great answer, I took this exercise from a repo which has some codility exercises: github.com/bitoiu/codility/tree/master/complementary_pairs. It specifically asks for a sub quadratic answer, but like you say, this might dwell on a number trick that would make computing it more trivial. thanks again.
• Vedran Šego: Scratch that. I've missed the part about pairs. My answer proved only that all sums cannot be found in sub-exponential time (actually, sometimes such problem has infinitely many solutions!). IMO, you should accept one of the other two answers instead of mine.

Answer 3

It seems to me you can get faster than quadratic if you sort the list first, and use an algorithm like this... (JSFiddle)

function complementaryPairs(a, target) {
 var count = 0,
 left = 0,
 right = a.length - 1,
 i;
 a.sort(function (a, b) {
 return a - b
 }); // [-3, -2, 0, 1, 1, 3, 3, 3, 4, 5, 8]
 // Eliminate arrays that can't contain any pairs
 if (a[left] * 2 > target || a[right] * 2 < target) {
 return 0;
 }
 for (; left <= right && a[left] * 2 <= target; left++) {
 // Get rid of any values on the right that are too large 
 while (right > left && a[left] + a[right] > target) right--;
 // Count values in between left and right which match with left
 for (i = right; i > left && a[left] + a[i] == target; i--) {
 count += 2;
 }
 }
 // Any values that are exactly half the target can also complement themselves
 // so count them again
 while (a[--left] * 2 == target) {
 count++;
 }
 return count;
}

As the starting point for right decreases upon each cycle of left, it must be less than quadratic, right? (I'm happy to be corrected on this.)

And the built in sort is, as far as I know, O(n log n), so we can use it without increasing the order of complexity. (Of course in a high level language this becomes irrelevant because any built in function is likely to be much faster than one we would write ourselves).

Edit: here's an alternative version which I think is slightly faster and makes it easier to see how it works. This is pretty clearly O(n), apart from the initial sort (isn't it...?) (JSFiddle)

function complementaryPairs(a, target) {
 var count = 0;
 a.sort(function (a, b) {
 return a - b
 }); 
 for (var left = 0, right = a.length - 1; left < right;) {
 if (a[left] + a[right] < target) {
 left++;
 } else if (a[left] + a[right] > target) {
 right--;
 } else if (a[left] == a[right]) {
 // Shortcut if the value is target / 2
 return count + (right - left + 1) * (right - left + 1)
 } else {
 // Found complementary pair. Move towards middle, counting duplicates.
 for (var leftCount = 1; a[left] == a[++left]; leftCount++);
 for (var rightCount = 1; a[right] == a[--right]; rightCount++);
 count += leftCount * rightCount * 2;
 }
 }
 return count;
}

• bitoiu: the inner loop for / for is always quadratic even if it's not pure n*n
• Vedran Šego: @bitoiu It's not. Notice that j is never reset. This means it gets to go only once from a.length - 1 down to, in the worst case, zero during an execution of a program. That makes the first inner loop overall linear in a.length. The second one (by k) is similar.
• bitoiu: @VedranŠego I might have this assumption wrong, that anything which is N* (N -C), whatever C, this will eventually lead to N*N? again, might be me being a noob.
• Stuart: @bitoiu The point is that C is not a constant but is increasing with each iteration of the outer loop
• Vedran Šego: @bitoiu Consider this: for (i = 0; i < n; i += 2) for (j = i; j % 7 > 0; j++) k++; It's two loops, but the inner one runs at most 7 times each time, so it runs at most 7n/2 times. It's linear. In Stuart's code, consider only variable j and ignore the second inner loop for a moment. What happens with j? It starts from j = a.length - 1 and stops, if not before, when j = 0 (because j > i >= 0). It happens through many steps of the outer loop, but it still catches each value only once and, hence, gets at most a.length - 1 steps. I hope it is more clear now.

Answer 4

Using a dictionary to look up is better:

private static int solution(int k, int[] arr) {
 Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
 for(int item: arr) {
 map.put(item, true);
 }
 int count = 0;
 for(int item: arr) {
 int temp = k - item;
 if(map.containsKey(temp)) {
 count ++;
 }
 }
 return count;
}

• IEatBagels: Hello duybinh0208, you should explain why using the dictionary is better than the approach the OP provided, this makes for a better review :)
• pacmaninbw: You will get an up vote if you answer @IEatBagels question.

Answer 5

This is computable in linear time by creating a hashtable (H) mapping each value in the array to the number of times it appears (a multiset).

A: [1, 8, -3, 0, 1, 3, -2, 4, 5] }
H: { -3 => 1, -2 => 1, 0 => 1, 1 => 2, 3 => 1, 4 => 1, 5 => 1, 8 => 1 }

Then the number of complementary pairs is

sum(over i in H.keys) { h[i] * h[K-i]) / 2 }