Pair of Numbers to obtain given sum

Introduction

This problem is already defined in one of the previous post. You can read that to know the problem in more detail. The definition goes like this, find a pair of numbers to obtain given sum in an array. The task is to find two numbers in an array which when added will produce a desired sum.

Approach to find a Pair of Numbers to obtain given sum

As the theory is already mentioned in the previous post, let us directly jump to all possible solutions. Here I am defining three different solutions to this problem. And the idea is to build a basic understanding and then proposing the brute force solution. Then improving to a efficient solution. We will also consider a special case, where the input array is already sorted.

Brute Force Approach

How can we find the required pair in a long array. The obvious way would be to find out all pairs, and the moment we find the sum just return the pair. This is an awesome solution, with very simple code.

This means, iterate through the first array and for each element in first array check its sum with all elements in the second array. If the sum is found, return.

Source Code

Analysis

Clearly this is a quadratic solution, we are iterating whole length of second array for each element of the first array. You can argue that we are actually not iterating through all the elements in the second array, which is true.

For first element of A, we iterate through N-1 elements of the second array. For the second element, we iterate through N-2 elements and so on. Hence, total number of elements evaluated would be N+ (N-1) + (N-2)+ … + 1 which is equal to (N(N+1) /2). For asymptotic calculations it is O(N^2)

Good news, we do not consume any extra space, hence the space complexity is O(1)

Efficient Approach

Can we do better?

Of course we can try doing better, let us try to this using a HashMap. Let the map contain the frequency of each number in the array. Once this map is prepared, we can traverse through the array and for each element, in the array, we can find another element in the map which complements it to get the desired sum.

For e.g. If the array contains 8, 5, 9, 6, 3, 3 and the desired sum is 8. Then we can create a frequency map which will contain the following entries [{8, 1}, {5, 1}, {9, 1}, {6, 1}, {3, 2}].

Now when we iterate through the array and evaluate each element, then for the element 8 we need another element 0 to get a sum 8. Clearly the map doesn’t have an element 0. So, we evaluate the next element which is 5 and to get a sum 8 we need a 3. The map contains 3, so the pair which results in a sum of 8 is 5 and 3.

This approach is awesome, it requires two passes of the array, one to create the frequency map and the other two evaluate the sum. But what if the desired sum is 10. This approach will return 5 and 5 which definitely is wrong.

There is only one 5 in the array, so we need to make an explicit check for frequency to be at least 2 for numbers where the number we are evaluating is SUM/2.

Source Code

Analysis

The running time of this algorithm is linear. We can see that we iterate the array two times. Lookup in a Hash Map is amortized constant time O(1). So we can say that running time is O(N) .

The auxiliary space required is linear, in worst case, the array will have unique elements. So the hash map will have one entry per element. Hence, we can say space complexity is O(N). We achieved some run time improvement by trading off some space.

For Sorted Arrays

A special case for this problem is a sorted input array. The solution is slightly tricky and might need some thought. Let us first examine the properties of a sorted array

  • All the elements are arranged in their natural ordering, either ascending or descending
  • This translates to the fact that the first element is the smallest and the last element is the largest.

Here is a sorted array 1, 3, 5, 6, 7, 8, 9, 10 and the desired sum is 14

The idea is to have two pointers, one at the beginning of the array and the other at the end of the array. The following three cases arise:

  • The sum of these two elements is equal to the desired sum. In this case we just return the elements pointed by these two pointers
  • The sum of these two elements is smaller than the desired sum. That means, we need to test with some other element which increases the prospective sum.
    • Now, the only way to increase the sum of two numbers in a sorted array is to increment the pointer at the beginning.
    • We keep repeating this process until we either find the desired sum or the sum of the current two elements is more than the desired sum.
  • The sum of these two elements is greater than the desired sum. That means we need to test with some other element which decreases the prospective sum.
    • The only way to decrease the sum of two numbers in a sorted array is to decrease the pointer at the end
    • We keep repeating this process until we either find the desired sum or  the sum of the current two elements is less than the desired sum.
  • We break out of the loop when the two pointers cross each other.

By the end, we either have the pair or an indication that no such pair exists.

Source Code

Analysis

As we can see, we do not use any extra space. Hence the space complexity is O(1).

Talking about the running time of the algorithm, we only traverse the array once, hence it runs in linear time O(N).

Summary

This post explains how a problem can be solved in multiple ways. One thing we must realize is that, with some hints about the data or by utilizing some extra space, we cam improve the running time of the algorithm.

If the input array was not sorted, the third algorithm can’t even be applied. However, if we are looking for multiple queries on this data, the second solution will be a great one if the input array has a lot many duplicates.