Find if there exists a pair with a given sum in a sorted array.

Given an array of integers which are in ascending order and a sum. Our aim is to find if there is any pair of integers which total is equal to input sum.

Let us discuss this problem with below example.

Array {1, 2, 3, 4, 5, 8, 9 } and a sum 13 is given.

Above example contains numbers 4 & 9 which sum is equal to our input.

Our output here should be true.

We can solve this problem in three different approaches, though here we will only gives the best approach which solves this problem with linear complexity and constant time. Let’s first discuss all three different approaches and write code for the best solution.

  1. Two iterative loops.
    1. We can solve this problem using two iterative loops, which take up quadratic complexity.
    2. We check each value in the array with all other values until we find the sum.
  2. A hash map.
    1. In this approach, we solve using a hash map that needs an extra linear space.
    2. For each value, we search for (sum – value) on the map. If the result exists in the map, then the sum exists in the array. If no such element exists in the map, then we insert the value inside the map (value is index).
    3. We do the second step until the end of the array. If no such number found in the map then this function returns false.
  3. Start and end of the array.
    1. In this approach, we use a start and end indices of the array and calculates the sum of those values.
    2. The sum is equal to our input, we return true from there.
    3. If the sum is lesser than the input, then we move start to its next.
    4. If the sum is more significant, then we move end to its previous index.
    5. We do all the above steps iteratively until the start reaches the end index.

We choose the third approach here, because of its performance. This approach takes a linear time with constant complexity. Let’s see the code for this approach.

/*
    Solution with linear time complexity.
*/
bool findPairSum(int arr[], int size, int sum) {
    int start = 0;
    int end = size - 1;

    while (start < end) {
        int val = arr[start] + arr[end];
        if (val == sum) {
            return true;
        }
        else if (val < sum) {
            start++;
        }
        else {
            end--;
        }
    }
    return false;
}
Complexity: O(n)
Space: O(1)

Lets see the full program with driver code.

// Output
Found pair with sum 13.
Advertisements