Find the indices of pairs whose sum is x

Question

Given an array, I've to find the index of pairs whose sum is equal to x.

Suppose the array is arr[5] = 1 2 3 4 2 and sum = 5, then the pairs are (1,4), (2,3) and (3,2).

I need to store indices of pairs which are for

(1,4) => (0,3)
(2,3) => (1,2)
(3,2) => (2,4)

So the answer is: (0,3),(1,2),(2,4)

I'm using hash map. Here's my function:

pair<int,int> index[5];
int FindPairs(int arr[],int n, int sum) {
    int i, temp,count=0,seta[n],setb[n],j;
bool hash[MAX] = {0}; 
for(i = 0; i < n; ++i)  {
    temp = sum - arr[i];
    if(temp >= 0 && hash[temp]  == 1 ) 
           seta[count++] = i;
    hash[arr[i]] = 1;
}
if(count == 0) return 0;
for(i=0;i<count;++i){
    for(j=0;j<n;j++){
        if( (sum - arr[seta[i]]) ==arr[j]  ) {
            setb[i] = j;
            break;
        }
    }
}
for(i=0;i<count;++i)  index[i] = make_pair(seta[i],setb[i]);
return count;
}

Here:

• n is the size of array,
• seta[] consists of index of first number in the pair and
• setb[] consists of index of second number in the pair.

I'm using O(count*n) for calculating the index of second number for every pair.

Is there any more efficient way to achieve this?

Answer 1

It might be a good idea to store, for each value, a list of indices that have that value:

const int MAX_VAL = 5;
std::vector<std::list<int>> mylist(MAX_VAL);
for (i = 0; i < n; ++i)
    mylist[arr[i]].push_back(i);

Then, for each value, find the "complementary" value, and print the list of all indices at which this value can be found.

for(i=0;i<n;++i){
    a = arr[i];
    b = sum - a;
    for (auto j: mylist[b])
        make_pair(i, j); // whatever you want to do with this pair of indices...
}

It might be worthwhile to check for i <= j to avoid printing the same pair twice.

Please note that the complexity for the general case has to be O(count*n): the worst case is for the array consisting of the same numbers:

Array: 1, 1, 1, 1, 1

Sum: 2

Answer: (0, 0), (0, 1), (0, 2), ..., (4, 4)

Complexity for printing: O(n^2), or O(count*n) because here count is equal to n

Answer 2

This is the same analysis as anatolyg's answer, but coded out using unordered_map.

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

void FindPairs(int arr[],int n, int sum, list<pair<int,int>> *pindex) {
  unordered_map<int,list<int>> etoi; // map entry to list of indices
  for( int i=0 ; i<n ; ++i ) etoi[arr[i]].push_back(i);
  for( int i=0 ; i<n ; ++i )
  {
    unordered_map<int,list<int>>::iterator it = etoi.find(sum-arr[i]);
    if( it != etoi.end() ) for( auto j: it->second )
      if( i < j ) pindex->push_back(make_pair(i,j));
  }
}

int main()
{
  int arr[5] = { 1, 2, 3, 4, 2 };
  int sum = 5;

  list<pair<int,int>> index;
  FindPairs( arr, sizeof(arr)/sizeof(int), sum, &index );
  for( auto p: index ) cout << '('<<p.first<<','<<p.second<<") ";
  cout << endl;
}

Output:

(0,3) (1,2) (2,4)