Check for pair in an array with a given sum

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

Key takeaway

• 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 check whether there is a pair of elements in the array whose sum is equal to targetSum. If yes, return true; otherwise, return false.

• 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 of 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

Solution idea and steps

One basic solution is to check each possible pair. If there exists a pair (i, j) with a sum equal to targetSum, we return true. To achieve this: We run two nested loops to explore all possible pairs: the outer loop from i = 0 to n - 2 and the inner loop from j = i + 1 to n - 1.

Inside the inner loop, we check if the sum of the current pair (X[i] and X[j]) is equal to the targetSum. If it is, we return true. By the end of the nested loops, there is no such pair in the array and we return false.

Solution pseudocode

checkPairSum(X, n, targetSum)
    // Check every pair of distinct elements
    for i from 0 to n - 2
        for j from i + 1 to n - 1
            // Return true if this pair sums to the target
            if X[i] + X[j] == targetSum
                return true
    // No pair sums to the target
    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²). So time complexity = O(n²). We are using constant extra space, so space complexity = O(1).

Using sorting and binary search

Solution idea

The critical question is: How can we improve the time complexity? On a sorted array, binary search will take O(log n) time. Can we solve this problem using sorting and binary search? Let's think!

For every element X[i], if targetSum - X[i] is present in the array, then there exists a pair with targetSum. So one idea is to sort the array and apply binary search to find targetSum - X[i] for every element X[i]. If targetSum - X[i] is present, we return true.

Solution steps

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

Solution pseudocode

binarySearch(X, l, r, key)
    while l <= r
        mid = l + (r - l) / 2

        if X[mid] == key
            return true

        if X[mid] < key
            l = mid + 1
        else
            r = mid - 1

    return false

checkPairSum(X, n, targetSum)
    sort X in ascending order

    for i from 0 to n - 1
        complement = targetSum - X[i]

        if binarySearch(X, 0, n - 1, complement)
            return true

    return false

Solution analysis

Suppose we are using the O(nlogn) sorting algorithm heap sort and iterative binary search for the implementation. 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 optimise the above approach further? Instead of applying binary search, can we think some different method to search for a pair in the sorted array? Let's explore!

On a sorted array, sometimes two pointers approach works perfectly. Here is a thought process: Suppose we sort the array and walk two pointers inward from both ends of the array, looking at their sum at each point. 

• If the sum is equal to targetSum, we found a pair. 
• If the 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 the 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. 
• If both pointers cross each other, then no such pair is present in the array.

Solution steps

Step 1: We sort the array in increasing order.

Step 2: Now we initialise two pointers: l = 0 and r = n - 1.

Step 3: Next, we run a while loop till l < r.

• If X[l] + X[r] == targetSum, we return true.
• If X[l] + X[r] < targetSum, we increment l by 1 to move towards a larger value of the pair sum. The idea is simple: Array is sorted and all pairs (l, r - 1), (l, r - 2), ..., (l, l + 1) will have sum less than targetSum. So, by incrementing l, we discard these possibilities of pairs in one go.
• If X[l] + X[r] > targetSum, we decrement r by 1 to move towards a smaller value of the pair sum. The idea is simple: Array is sorted and all pairs (l + 1, r), (l + 2, r), ..., (r - 1, r) will have sum greater than targetSum. So, by decrementing r, we discard these possibilities of pairs in one go.

Step 4: By the end of the loop, if we haven't found such a pair in the entire array, we return false.

Solution pseudocode

checkPairSum(X, n, targetSum)
    sort X in ascending order

    l = 0
    r = n - 1

    while l < r
        currentSum = X[l] + X[r]

        if currentSum == targetSum
            return true
        else if currentSum < targetSum
            l = l + 1
        else
            r = r - 1

    return false

Solution analysis

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

Overall time complexity = Time complexity of heap sort + Time complexity of the while loop = O(n log n) + O(n) = O(n log n). In the code, we are using constant extra space because heap sort is an in-place sorting algorithm. So space complexity is O(1).

Efficient approach using a hash table

Solution idea

In the last two solutions, the time complexity is still in the range of O(nlogn) due to the dominance of the sorting algorithm. The critical question is: Can we optimise further to solve it using linear time complexity? If we observe the above solutions, searching is a critical operation. So one idea would be to use a hash table because the hash table performs searching efficiently in the O(1) average.

Here is an idea: We iterate over each array element and insert element X[i] into the Hash table. Before inserting X[i], we check if the 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

1. We create a hash table to store array elements.
2. Now we run a loop and scan the array for each X[i].
3. 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. 
4. If we didn’t find any such pair by the end the loop, return false.

Solution pseudocode

checkPairSum(X, n, targetSum)
    hashTable = empty set

    for i from 0 to n - 1
        complement = targetSum - X[i]

        if hashTable contains complement
            return true

        hashTable.insert(X[i])

    return false

Solution analysis

In the worst case, we need to scan the whole array to find such a pair. So time complexity = Time complexity of inserting elements into the hash table + Time complexity of searching targetSum - X[i] into the hash table = n * O(1) + n * O(1) = O(n) + O(n) = O(n). Space complexity = O(n), as we are using a hash table of size O(n).

Critical ideas to think!

• Is there any other way to solve this problem?
• What would be the time and space complexity of the last approach if we use a binary search tree (BST) instead of a hash table?
• What would be the time and space complexity of the 2nd and 3rd approaches if we use the quicksort or merge sort algorithms?
• Do all the above algorithms work fine if elements are repeated?
• In all the above approaches, do we need to handle the case for negative values separately? How can we modify the above code to return the pair with the targetSum?
• How can we modify the above code to count all pairs with the targetSum?
• What are the differences between Hash Set and Hash Map in Java?
• What are the differences between unordered map and unordered set in C++?

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!