Finding the number of pairs in array with given difference

Problem solving with programming: Finding the number of pairs in array with given difference

Given an array of N distinct values, how to find the number of pairs with a difference of K?

X. Sort first

1. Take two indices and point them to first and second elements.
2. Repeat the following steps until any index reaches the end of the array
1. If the difference matches, increment count and increment both the indices
2. If the difference is less than required value,  increment second index
3. Otherwise increment first index.

int findPairsWithDiff( vector<int> &array, int diff )


{


 sort( array.begin(), array.end() );


 


 int matches = 0;


 int size = array.size();


 if ( size > 1)


 {


  int i,j;


  i = 0;


  j = 1;


  


  while ( i < size && j < size )


  {


   if( i != j && (array[j]-array[i]) == diff )


   {


    matches++; 


    i++; // if not distinct, use while lopp to skip same element same as i,j


    j++;


   }


   else if( (array[j]-array[i]) < diff )


    j++;


   else


    i++;


  }


 }


 return matches;


}

X. Use HashSet ==< if not distinct, then use HashMap.
No need visited array, remove from set directly.

1. Store all the array elements into a set.
2. For each element in the array do the following.
1. If the set contains array[i]+diff or array[i]-diff, increment the diff count. 
2. Remove array[i] from the set.

int findPairsWithDiff1( vector<int> &array, int diff )


{


 int matches = 0;


 int size = array.size();


 if ( size > 1)


 {


  set<int> numSet;


  


  for( int i = 0; i < size; i++ )


  {


   numSet.insert(array[i]);


  }


  


  for( int i = 0; i < size; i++ )


  {


   if( numSet.find(array[i]+diff) != numSet.end() ||


    numSet.find(array[i]-diff) != numSet.end()


     )


   {


    matches++;


   }


   numSet.erase( numSet.find(array[i]) );


  }


 }


 return matches;


}

Read full article from Problem solving with programming: Finding the number of pairs in array with given difference