Check for pair in an array with a given sum

Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Flipkart, Hike, Morgan Stanley

Key takeaway:

• This is an excellent problem to learn problem-solving using various approaches.
• Two-pointers and hash table solutions are worth exploring.
• One can find several variations of this problem asked during a coding interview.

Let’s understand the problem

Given an array of n integers and a value targetSum, write a program to determine whether there is a pair of elements in the array that sum exactly to targetSum. In other words, we need to determine whether two elements exist in the array whose sum is equal to targetSum.

• We assume all elements are distinct.
• Values in the array can be both negative and positive.

Example 1

Input: X[] = [-5, 1, -40, 20, 6, 8, 7], targetSum = 15, Output: true

Explanation: (7, 8) or (-5, 20) are the pairs with the sum 15.

Example 2

Input: X[] = [-5, 4, -2, 16, 8, 9], targetSum = 15, Output: false

Explanation: There is no pair of elements whose sum is equal to 15.

Discussed solution approaches

• Brute force approach using nested loops
• Using sorting and binary search
• Using sorting and two pointers approach
• Efficient approach using hash table

Brute force approach using nested loops

A simple idea would be to use two nested loops and check each pair (i, j) in X[]. If there exists a pair with a sum equal to targetSum, we return true. Otherwise, if we don’t find any such pair by the end of nested loops, we return false.

Solution code C++

bool checkPairSum(int X[], int n, int targetSum)
{
    for (int i = 0; i < n; i = i + 1)
    {
        for (int j = i + 1; j < n; j = j + 1)
        { 
            if (X[i] + X[j] == targetSum)
                return true;
        }
    }
    return false;
}

Solution code Python

def check_pair_sum(X, n, target_sum):
    for i in range(n):
        for j in range(i + 1, n):
            if X[i] + X[j] == target_sum:
                return True
    return False

Solution analysis

We are exploring all possible pairs in the array and doing constant operations for each pair. Total number of possible pairs = nC2 = n(n - 1)/2 = O(n²). Time complexity = O(n²). We are using constant extra space, so space complexity = O(1).

The critical question is: How can we improve the time complexity further?

Using sorting and binary search

Solution idea

Another idea would be to sort the array and apply binary search for every X[i] to find targetSum - X[i]. If targetSum - X[i] is present, we return true. Otherwise, we return false. Binary search performs searching in O(logn), which could help us to improve time complexity.

Solution steps

• We sort the array in increasing order.
• Now we run a loop for each element X[i] and apply binary search to look for an element with value equal to targetSum - X[i].
• If targetSum - X[i] exists, return true.
• We return false if there is no such a pair in the array.

Solution code C++

bool binarySearch(int X[], int l, int r, int key)
{ 
    while (l <= r) 
    { 
        int mid = l + (r - l) / 2;
        if (X[mid] == key) 
            return true;
        if (X[mid] < key) 
            l = mid + 1;
        else
            r = mid - 1;
    }
    return false;
}

bool checkPairSum(int X[], int n, int targetSum)
{
    sort(X, X + n);
    for(int i = 0; i < n; i = i + 1)
    { 
        int k = binarySearch(X, 0, n - 1, targetSum - X[i]);
        if (k == true) 
            return true;
    }
    return false;
}

Solution code Python

def binary_search(X, l, r, key):
    while l <= r:
        mid = l + (r - l) // 2
        if X[mid] == key:
            return True
        elif X[mid] < key:
            l = mid + 1
        else:
            r = mid - 1
    return False

def check_pair_sum(X, n, target_sum):
    X.sort()
    for i in range(n):
        k = binary_search(X, 0, n - 1, target_sum - X[i])
        if k:
            return True
    return False

Solution analysis

Suppose we use efficient O(nlogn) sorting algorithm heap sort and iterative binary search to search targetSum - X[i]. Time complexity = Time complexity of heap sort + n * Time complexity of binary search = O(nlogn) + n* O(logn) = O(nlogn) + O(nlogn) = O(nlogn).

Space complexity = Space complexity of heap sort + Space complexity of the iterative binary search = O(1) + O(1) = O(1).

Using sorting and two pointers approach

Solution idea

Can we optimize the above approach and find a different method to search for a pair in the sorted array? Can we think of applying two pointers approach because sometimes it works perfectly in the sorted array? Let’s think!

We sort the array in increasing order and then walk two pointers inward from both ends of the array, looking at their sum at each point. 

• If pair sum is equal to targetSum, we return true.
• If sum is greater than targetSum, then any sum using the larger element will be greater than targetSum, so we move the right pointer inwards towards a smaller sum. 
• If sum is less than targetSum, then any sum using the smaller element is less than targetSum, so we move the left pointer inwards towards a larger sum. 
• By the end of above process, if both pointers cross each other, any such pair is not present in the array, and we return false.

Solution steps

1. We sort the input array in increasing order.
2. Now we initialize two pointers, left pointer l = 0, and right pointer r = n - 1
3. We run a loop while l < r.
4. If (X[l] + X[r] == targetSum), then we return true.
5. if( X[l] + X[r] < targetSum), then we increment l by 1.
6. if( X[l] + X[r] > targetSum), then decrement r by 1

If didn’t find such a pair in the whole array, we return false.

Solution code C++

bool checkPairSum(int X[], int n, int targetSum)
{
    sort(X, X + n);
    int l = 0, r = n - 1;
    while (l < r)
    {
        if (X[l] + X[r] == targetSum)
            return true;
        else if (X[l] + X[r] < targetSum)
            l = l + 1;
        else
            r = r - 1;
    }
    return false;
}

Solution code Python

def check_pair_sum(X, n, target_sum):
    X.sort()
    l = 0
    r = n - 1
    while l < r:
        if X[l] + X[r] == target_sum:
            return True
        elif X[l] + X[r] < target_sum:
            l = l + 1
        else:
            r = r - 1
    return False

Solution analysis

Suppose we use an in-place O(nlogn) sorting algorithm heap sort. The critical question is: What would be the time complexity of the two-pointers while loop? Here is an idea: Based on the comparison, we are moving either the left or right pointer by 1. In the worst case, we will access each array element using two pointers. So time complexity of two pointers while loop = O(n).

Overall time complexity = Time complexity of heap sort + Time complexity of while loop = O (nlogn) + O(n) = O (nlogn). Space complexity = O(1) because we use constant extra space.

Efficient approach using hash table

Solution idea

We improved time complexity in the last two solutions, but it is still in the range of O(nlogn) due to the dominance of sorting algorithm. The critical question is: How can we optimize further to solve it using linear time complexity?

If we observe above solutions closely, searching is a critical operation. The best idea would be to use a hash table to improve time complexity further because it performs searching efficiently in the O(1) average.

So we iterate over each array element and insert element X[i] into the Hash table. Before inserting X[i], we check if value targetSum - X[i] already exists in the table. If it exists, we have found a pair with a sum equal to targetSum.

Solution steps

• We take a hash table of size equal to n.
• We run a loop and scan the array for each X[i]. We check if targetSum - X[i] is present in the hash table or not. If yes, we have found a pair and we return true. If no, we insert X[i] into the Hash table. 
• If we didn’t find any such pair by the end of loop, return false.

Solution pseudocode

bool checkPairSum(int X[], int n, int targetSum)
{ 
    Hash Table H
    for (i = 0; i < n; i = i + 1)
    { 
        int k = targetSum - X[i]
        if (H.search(k) == true) 
            return true
        H.insert(X[i])
    } 
    return false
}

Solution code C++

bool checkPairSum(int X[], int n, int targetSum)
{
    unordered_map<int, bool> H;
    for (int i = 0; i < n; i = i + 1)
    {
        int k = targetSum - X[i];
        if (H.count(k) > 0)
            return true;
        H[X[i]] = true;
    }
    return false;
}

Solution code Python

def check_pair_sum(X, n, target_sum):
    H = {}
    for i in range(n):
        k = target_sum - X[i]
        if k in H:
            return True
        H[X[i]] = True
    return False

Solution code Java

public class Solution
{
    public boolean checkPairSum(int[] X, int n, int targetSum) 
    {
        HashMap<Integer, Boolean> H = new HashMap<>();
        for (int i = 0; i < n; i = i + 1) 
        {
            int k = targetSum - X[i];
            if (H.containsKey(k))
                return true;
            H.put(X[i], true);
        }
        return false;
    }
}

Solution analysis

In the worst case, we need to scan the whole array to find such a pair. So searching and insertion in the hash table are critical operations. Time complexity = Time complexity of inserting n elements into the hash table + Time complexity of searching targetSum - X[i] n times into the hash table = n. O(1) + n . O(1) = O(n) + O(n) = O(n).

Space complexity = O(n). We are using a hash table of size O(n).

Critical ideas to think!

• Is there any other way to solve this problem? Think!
• In the last approach, what would be the time and space complexity if we use BST instead of a hash table? 
• In the 2nd and 3rd approaches, what would be the time and space complexity if we use quicksort or merge sort algorithm?
• Is all the above algorithm works fine if elements are repeated?
• Why the idea of the two-pointers approach works perfectly for a sorted array? Provide proof of correctness for the two-pointers approach.
• In all the above approaches, do we need to handle the case for negative values separately?
• How do we modify the above code if we need to return a pair with the targetSum?
• How do we modify the above code if we need to count all pairs with the targetSum?

Comparisons of time and space complexities

• Nested loops: Time = O(n^2), Space = O(1)
• Sorting and binary search: Time = O(nlogn), Space = O(1)
• Sorting and two pointers: Time = O(nlogn), Space = O(1)
• Hash table: Time = O(n), Space = O(n)

Similar coding questions to explore

• Find four elements that sum to a given value
• Find a triplet whose sum is equal to zero
• Given two unsorted arrays, find all pairs whose sum is x
• Count all distinct pairs with a difference equal to k
• Find intersection of two unsorted arrays
• Check whether array is subset of another array
• Find if there is a pair with a product equal to x

Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!