Algorithms to find complemantary pairs of numbers in an array

Let’s start this blog with a small coding problem that I came across a few days ago. The problem is to find in an array A of int values the number of all pairs of indices (i,j) so that A[i] + A[j] == K. For example, let A = { 1, 5, 9 } with K = 10 we get the pairs (0, 2), (2,0), and (1,1) and the result of the algorithm should be 3.

An obvious and easy solution looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int comp_pairs( int K, int[ ] A )
{
  int count = 0;
 
  for ( int i = 0; i < A.length; i++ )
  {
    for ( int j = i; j < A.length; j++ )
    {
      if ( A[ i ] + A[ j ] == K )
      {
        if ( i != j )
	{
	  count += 2;
	}
	else
        {
	  count++;
	}
      }
    }
  }
 
  return count;
}

Obviously, this solution has O(N^2) runtime complexity. Can we do better? Let’s have a look at the following solution.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int comp_pairs( int K, int[ ] A )
{
  Map<Integer, Integer> B = new TreeMap<Integer, Integer>( );
 
  for ( int i = 0; i < A.length; i++ )
  {
    final int k = A[ i ];
    final int tempValue = B.containsKey( k ) ? B.get( k ) : 0;
    B.put( k, tempValue + 1 );
  }
 
  Integer[ ] C = new LinkedList<Integer>( B.keySet( ) ).toArray( new Integer[ 0 ] );
  int l = 0;
  int r = C.length - 1;
  int count = 0;
 
  while ( l <= r )
  {
    if ( C[ l ] + C[ r ] == K )
    {
      final int c1 = B.get( C[ l ] );
      final int c2 = B.get( C[ r ] );
 
      count += ( l != r ) ? 2 * c1 * c2 : c1 * c1;
 
      l++; 
      r--;
    }
    else if ( C[ l ] + C[ r ] < K )
    {
      l++;
    }
    else
    {
      r--;
    }
  }
  return count;
}

The idea is to first remove all double values from the array and count them. We use a TreeMap to have the set of unique values sorted. Finally, we run on the array of sorted values from left and right to the middle. Once we have found a K-complementary pair, we determine the number of combinations of these two values. The runtime complexity of this solution is O( n log(n) ), because we have to sort the array.

Can we do better? When we search for this problem, we can find the following solution on StackOverflow. Look here for the original answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int foo_opt( int k, int[ ] A )
{
  Map<Long, Integer> C = new HashMap<Long, Integer>( );
  for ( int i = 0; i < A.length; i++ )
  {
    final long complValue = ( ( long ) k ) - A[ i ];
    final int tempValue = C.containsKey( complValue ) ? C.get( complValue ) : 0;
    C.put( complValue, tempValue + 1 );
  }
 
  int counter = 0;
  for ( int i = 0; i < A.length; i++ )
  {
    final long value = A[ i ];
    counter += C.containsKey( value ) ? C.get( value ) : 0;
  }
 
  return counter;
}

This solution has a runtime complexity of O(N).