Find all pairs of integers within an array which sum to a specified value

Question

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

I have tried this problem using a hash table to store entries for the sum of array elements, but it is not an efficient solution.

What algorithm can I use to solve this efficiently?

Answer 1

I don't see why the hash table approach is inefficient, at least in algorithm analysis terms - in memory locality terms admittedly, it can be quite bad. Anyway, scan the array twice...

First scan - put all the array elements in the hash table - O(n) total. Individual inserts are only amortized O(1), but a neat thing about how amortized analysis works means the O(n) is absolute - not amortized.

Second scan - check for (sum - current) in the hash table - O(n) total.

This beats the O(n log n) sort-and-search methods, at least in theory.

Then, note that you can combine the two scans into one. You can spot a pair as soon as you encounter the second of that pair during the first scan. In pseudocode...

for i in array.range
  hashset.insert (array [i])

  diff = sum - array [i]
  if hashset.includes (diff)
    output diff, array [i]

If you need positions of the items, use a hashmap and store item positions in it. If you need to cope with duplicates, you might need to store counts in a hashmap. For positions and duplicates, you might need a hashmap of start pointers for linked lists of positions.

This makes assumptions about the hash table implementation, but fairly safe ones given the usual implementations in most current languages and libraries.

BTW - combining the scans shouldn't be seen as an optimisation. The iteration overhead should be insignificant. Memory locality issues could make a single pass slightly more efficient for very large arrays, but the real memory locality issues will be in the hashtable lookups anyway.

IMO the only real reason to combine the scans is because you only want each pair reported once - handling that in a two-scan approach would be a bit more hassle.

Answer 2

1. If the array is sorted:

   Let i = 0, j = end of array, sum = the value you are looking for, then do:

   If i+j = sum, then output (i,j).
   If i+j < sum, then move i to the right one position.
   If i+j > sum, then move j to the left one position.

   Time complexity: O(n). Space complexity: O(1).

2. If the array is not sorted, there are a few ways to approach this problem:

   1. Sort the array and then use the above approach.

   2. HashMap:

      Store all elements in a HashMap.

      a+b=sum, so b=sum-a. For each element a of the array, look up b from the HashMap.

      HashMap lookup takes amortized O(1).

      Time complexity: O(n). Space complexity: O(n).

   3. BitMap:

      Iterate through the input to create a bitmap where each bit corresponds to an element value. Say the input is {2,5,8}, then we toggle the bitmap array's indices 2, 5 and 8 from binary 0 to 1. This takes O(1) per element, thus O(n) in total.

      Go through the input again. We know b=sum-a, so for every element a in the input, look up its b, which can be done in O(1) since it's a bitmap index. This also takes O(n) in total.

      Time complexity: O(n) + O(n) = O(n). Space complexity: bitmap space = O(n).

Answer 3

You don't even need to store all the elements in hashmap, and then scan. You can scan during the first iteration itself.

void foo(int[] A, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int e : A) {
        if (set.contains(sum-e)) {
            System.out.println(e + "," + (sum-e));
            // deal with the duplicated case
            set.remove(sum-e);
        } else {
            set.add(e);
        }
    }
}

Answer 4

How about sorting the array, then marching in from both ends?

Answer 5

Assume required sum = R

1. sort the array
2. for each number in the array A(n), do a binary search to find the number A(x) such that A(n) + A(x) = R

Answer 6

If you don't mind spending O(M) in space, where M is the sum you are seeking, you can do this in O(N + M) time. Set sums[i] = 1 when i <= M on a single pass over N, then check (sums[i] && sums[M-i]) on a single pass over M/2.

Answer 7

Implemented in Python 2.7:

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
    print str(n[0]) + " + " + str(n[1])

Output:

1 + 4
2 + 3

Answer 8

We can use C++ STL map to solve this

void subsetSum(int arr[], int n, int sum)
{
    map<int, int>Map;

    for(int i=0; i<n; i++)
    {
        Map[arr[i]]++;
        if(Map.count(sum-arr[i]))
        {
            cout<<arr[i]<<" "<<sum-arr[i]<<"\n";
        }
    }
}

Answer 9

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   //max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Answer 10

Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes array is sorted. The solution runs in O(n) time and does not use any extra memory aside from variable.

var count_pairs = function(_arr,x) {
  if(!x) x = 0;
  var pairs = 0;
  var i = 0;
  var k = _arr.length-1;
  if((k+1)<2) return pairs;
  var halfX = x/2; 
  while(i<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=i) pairs+=(comb++);
        break;
      }
      // count pair and k duplicates
      pairsThisLoop++;
      while(_arr[--k]==curK) pairsThisLoop++;
      // add k side pairs to running total for every i side pair found
      pairs+=pairsThisLoop;
      while(_arr[++i]==curI) pairs+=pairsThisLoop;
    } else {
      // if we are at a mid point
      if(curK==curI) break;
      var distK = Math.abs(halfX-curK);
      var distI = Math.abs(halfX-curI);
      if(distI > distK) while(_arr[++i]==curI);
      else while(_arr[--k]==curK);
    }
  }
  return pairs;
}

So here it is for everyone.

Start at both side of the array and slowly work your way inwards making sure to count duplicates if they exist.

It only counts pairs but can be reworked to

• find the pairs
• find pairs < x
• find pairs > x

Enjoy and don't forget to bump it if its the best answer!!

Answer 11

A solution that takes into account duplicates and uses every number only one time:

void printPairs(int[] numbers, int S) {
    // toMap(numbers) converts the numbers array to a map, where
    // Key is a number from the original array
    // Value is a count of occurrences of this number in the array
    Map<Integer, Integer> numbersMap = toMap(numbers); 

    for (Entry<Integer, Integer> entry : numbersMap.entrySet()) {
      if (entry.getValue().equals(0)) {
        continue;
      }
      int number = entry.getKey();
      int complement = S - number;
      if (numbersMap.containsKey(complement) && numbersMap.get(complement) > 0) {
      for (int j = 0; j < min(numbersMap.get(number), 
                              numbersMap.get(complement)); j++) {
        if (number.equals(complement) && numbersMap.get(number) < 2) {
           break;
        }
        System.out.println(number, complement);
        numbersMap.put(number, numbersMap.get(number) - 1);
        numbersMap.put(complement, numbersMap.get(complement) - 1);
      }
    }
  }
}

Answer 12

Hashtable solution, in Ruby (quite straightforward to understand):

value = 100
pairs = [1,99,5,95]
hash_of_pairs = {}

pairs.map! do |pair|
  # Adds to hashtable the pair
  hash_of_pairs[pair] = pair

  # Finds the value the pair needs
  new_pair = hash_of_pairs[value - pair]

  # Returns the pair whenever the pair exists, or nil
  [new_pair, pair] if !new_pair.nil?
end.compact! # Cleans up the array, removing all nil values

print pairs # [[1,99], [5,95]]

Answer 13

@Test
public void hasPairWithSum() {
  assertFalse(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 3, 9 }, 8));
  assertTrue(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 4, 4 }, 8));

  assertFalse(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 3, 9 }, 8));
  assertTrue(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 4, 4 }, 8));

  assertFalse(hasPairWithSum_Unsorted_Linear(new int[] { 9, 1, 3, 2 }, 8));
  assertTrue(hasPairWithSum_Unsorted_Linear(new int[] { 4, 2, 1, 4 }, 8));

  assertFalse(hasPairWithSum_Unsorted_Quadratic(new int[] { 9, 1, 3, 2 }, 8));
  assertTrue(hasPairWithSum_Unsorted_Quadratic(new int[] { 4, 2, 1, 4 }, 8));
}

private boolean hasPairWithSum_Ordered_Logarithmic(int[] data, int sum) {
  for (int i = 0; i < data.length; i++) {
    int current = data[i];
    int complement = sum - current;
    int foundIndex = Arrays.binarySearch(data, complement);
    if (foundIndex >= 0 && foundIndex != i) {
      return true;
    }
  }
  return false;
}

private boolean hasPairWithSum_Ordered_Linear(int[] data, int sum) {
  int low = 0;
  int high = data.length - 1;
  while (low < high) {
    int total = data[low] + data[high];
    if (total == sum) {
      return true;
    } else if (total < sum) {
      low++;
    } else {
      high--;
    }
  }
  return false;
}

private boolean hasPairWithSum_Unsorted_Linear(int[] data, int sum) {
  Set<Integer> complements = Sets.newHashSet();
  for (int current : data) {
    if (complements.contains(current)) {
      return true;
    }
    complements.add(sum - current);
  }
  return false;
}

private boolean hasPairWithSum_Unsorted_Quadratic(int[] data, int sum) {
  for (int i = 0; i < data.length; i++) {
    int current = data[i];
    int complement = sum - current;
    for (int j = 0; j < data.length; j++) {
      if (data[j] == complement && i != j) {
        return true;
      }
    }
  }
  return false;
}

Answer 14

Creating a hash table and then looking for value in it.

function sum_exist(num : number, arr : any[]) {
    var number_seen = {};
    for(let item of arr){
        if(num - item in number_seen){
            return true
        }
        number_seen[item] = 0;
    }
    return false;
}

Test case (using Jest)

test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(17 , [10, 15, 3, 7])).toEqual(true);
});


test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(16 , [10, 15, 3, 7])).toEqual(false);
});

Answer 15

#python 3.x
def sum_pairs(list_data, number):    
    list_data.sort()
    left = 0
    right = len(list_data)-1
    pairs = []
    while left < right:        
        if list_data[left]+list_data[right] == number:
            find_pairs = [list_data[left], list_data[right]]
            pairs.append(find_pairs)
            right = right-1
        elif list_data[left]+list_data[right] < number:
            left = left+1
        else:
            right = right-1
    return pairs