Find Pair of Numbers in Array with a Given Sum

Problem Definition

This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few:

  • Find Pair of Numbers in Array with a Given Sum – The array is unsorted and contains a given range of numbers bounded by min and max.
  • Find Pair of Numbers in Array with a Given Sum – The array is sorted and contains a given range of numbers bounded by min and max.
  • Find Pair of Numbers in Array with a Given Sum – The array contains unique numbers only.

In all the above versions, we have to return the indices in the array where the numbers are stored, which makes it slightly complicated and enforces us not to manipulate the original input array. Also, the problem statement guarantees that there is at least on such pair in the array.

There are few more versions but today we will focus on the generic version of the problem which is the first one. If we can solve the first one, the second and third one is a subset of it.

Approach – Find Pair of Numbers in Array with a Given Sum

Remember that the elements are not unique but they are bounded by a min and a max range. Let us understand the naive way of solving this problem.

The Naive Way

Calculate the sum of each pair and store it in a hashmap(key-value pair) such that the key is the sum of the pair and the value is (XX-YY) where XX is the index of the first element and YY is the index of the second element.

Now you can just iterate through the hashmap once and find the index pair whose sum matches to the given sum. If there are multiple such pairs then the problem becomes slightly complicated because the hash map in certain language overwrites the values if the key is duplicate.

So, one can try to swap the keys and values. This means the index pair (XX-YY) is the key and the sum is the value. This will handle the case of duplicates and works perfectly fine.

There might be some space and running time issues.

For e.g. The space required will be equal to the number of distinct sums in the first case and number of possible pairs in the second case. So, we can say that the upper bound of space is equal to the number of ways to select 2 items from a list of N numbers where N is the length of the input array and the order of selection doesn’t matter. This will be equal to C(N,2) which is (1/2) * N * (N-1) that is O(N2.

The running time would have the same upper bound because it needs to calculate the sum of all the pairs, considering adding two numbers is a constant time job. Running Time would be O(N2)

A smarter Approach

Say that the sum given is S.

  1. Find the minimum (Min) and maximum (Max) numbers from the array.
  2. In case the numbers are unique, we can allocate a boolean array of length (Max-Min).
    • Iterate through the input array and for each number C encountered, mark that index C in the boolean array as true.
    • Iterate through the boolean array and for each index i in the array if the index S-i and index i both contain true. Then we found our two numbers which can result in sum S.
    • Break the loop and iterate through the input array to find the numbers and report their indices.
  3. In case the array contains duplicates, we can allocate an int array of length (Max-Min) and initialize it with zeroes.
    • Iterate through the input array and for each number C encountered, increment the content of index C in the int array by 1.
    • Iterate through the int array and for each index i in the array if the index S-i and index i both are greater than zero. Then we found our two numbers which can result in sum S.
    • Break the loop and iterate through the input array to find the numbers and report their indices.

Source Code – Find Pair of Numbers in Array with a Given Sum

Here is the source code written in Java for the problem definition, this can be further optimized but it is sufficient to prove the idea.

Note: I didn’t take care of the minimum value in the array and the int array is declared for a larger range 0 – Max. But you can choose to add that restriction. This piece of code will just allocate a bigger array and the indices 0 – Min will be always filled with zeroes.

Analysis

The space complexity, it would be equal to the size of the new int array which can be sometimes large O(Max – Min). Hence, the algorithm is good for short ranged input arrays.

The running time, it is proportional to the space complexity as in the worst case it has to iterate through the complete int array, consider the case where the last two elements add up to the sum.

Hope you enjoyed reading. Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • هنگامه

    Thank you for great explanation. what is time complexity of your second proposed method (smarter one)?

    • Hey, thanks for the comment. As I have mentioned in the Analysis section, that "The running time, it is proportional to the space complexity as in the worst case it has to iterate through the complete int array, consider the case where the last two elements add up to the sum."

      So we can say that the time complexity is O(Max-Min) where Max is the largest number in the array and Min is the smallest number in the array.

      Please remember that this method is only good if you have a short range of numbers 🙂

  • Sunny

    import java.util.BitSet;
    <code>
    public class TwoNumbersSum {
    public int[] arr;
    public int sum;

    public void findTwoNumbers() {
    // Find Min in the arr
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
    min = arr[i];
    }
    if (arr[i] > max) {
    max = arr[i];
    }
    }

    // Create BitSet where index is
    // arr[i] – min
    // modifiedSum = sum – (2*min)
    BitSet bits = new BitSet(max);
    System.out.println("Original BitSet: " +bits);
    for (int elem : arr) {
    bits.set(elem – min);
    }
    System.out.println("BitSet after Array Traversal: " +bits);
    int modifiedSum = sum – (2*min);

    for (int i = 0; i < max; i++) {
    // At every index i in BitSet (which is a modified arr[i])
    System.out.println("At Index: " +i + " Other Index: " +(modifiedSum – i));
    if (bits.get(i) && (modifiedSum -i) > 0 && bits.get(modifiedSum – i)) {
    // Get original number in arr[] by adding min
    int a = i + min;
    int b = modifiedSum – i + min;
    System.out.println("Found Numbers a = " +a + " b = " +b);
    bits.set(i, false);
    bits.set(modifiedSum – i, false);
    }
    }
    }

    public static void main(String[] args) {
    TwoNumbersSum numbers = new TwoNumbersSum();
    numbers.arr = new int[] {4, 6, 7, 2, 1, 10};
    numbers.sum = 9;
    System.out.println("============> Find Numbers with Sum: " + numbers.sum);
    numbers.findTwoNumbers();

    numbers.arr = new int[] {-20, -15, -10, -17, 10, 15, 2, 3, 5};
    numbers.sum = 0;
    System.out.println("============> Find Numbers with Sum: " + numbers.sum);
    numbers.findTwoNumbers();
    }
    }
    </code>

    • Thank You Sunny, really appreciate your efforts in writing the complete code.