Check for pair in an array with a given sum

EnjoyAlgorithms Blog Cover Image

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

Key takeaway

  • A famous searching problem to learn problem-solving using various approaches.
  • The two-pointers and hash table solution are worth exploring.
  • One can find variations of this problem asked during a coding interview.

Let’s understand the problem

Given an array of n integers and given a number targetSum, write a program to determine whether there is a pair of elements in the array that sums to exactly 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 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.

Important note: Before moving to the solutions, we recommend learners solve this problem. If solved, then well done! We would like to hear your ideas in the comment. Otherwise, no problem, this is an opportunity to learn a new pattern in problem-solving!

Discussed solution approaches

  • A brute force approach  using nested loops
  • Using sorting and binary search
  • Using sorting and two pointers approach
  • An efficient approach  using a hash table

A 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, then we return true. Otherwise, if we didn’t find such a pair by end of nested loops, then we return false.

Solution Pseudocode

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 Analysis

We are exploring all possible pairs in the array and doing constant operations for each pair. Total no. 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). But 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 for every value X[i] and apply binary search to find value targetSum - X[i] in the array. Binary search performs searching in O(logn) which could help us to improve the time complexity. If targetSum - X[i] is present then return true otherwise return false.

Solution Steps

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

Solution Pseudocode

bool checkPairSum (int X[], int n, int targetSum)
{
    heapSort(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
}

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
}

Solution Analysis

Suppose we are using efficient O(nlogn) sorting algorithm heap sort and implementing binary search iteratively 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-pointer approach

Solution Idea

Can we optimize the above approach further and find a different method to search a pair in the sorted array? Can we think to apply two pointer 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, at each point looking at their sum. If the sum of the pair is equal to targetSum, then we are done and return true. But if the sum exceeds the value of targetSum, then any sum using the larger element is too large, so we move the right pointer inwards towards a smaller sum. If the sum is less than targetSum, then any sum using the lower element is too small, so we move the left pointer inwards towards a larger sum. By the end of this process, if both pointers cross each other, the 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 in the sorted array, 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 return we 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
  7. If didn’t find such a pair in the whole array , we return false.

Solution Pseudocode

bool checkPairSum (int X[], int n, int targetSum)
{ 
    heapSort(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 Analysis

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

Overall time complexity = Time complexity of the heap sort + Time complexity of the while loop = O (nlog n) + O(n) = O (nlog n). Space complexity = O(1), we using constant extra space.

An efficient approach  using a hash table

Solution Idea

We improved the time complexity in the last two solutions, but it is still in the range of O(nlogn) due to the dominance of the sorting algorithm. So now the critical question: how can we optimize further to solve it using linear time complexity? If we observe the above solutions closely, searching is the critical operation for the solution. So the best idea is to use the hash table to improve the time complexity further because it performs searching efficiently in the O(1) average. Think!

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

Solution Steps

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

Solution Pseudocode

bool checkPairSum (int X[], int n, int targetSum)
{ 
    HashTable 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 Analysis

In the worst-case, we scan the whole array and didn’t find any such pair. So searching and insertion in the hash table are the 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).

Important Note: We recommend learners transform the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Enjoy programming!

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 a BST in place of a hash table? 
  • In the 2nd and 3rd approaches, what would be the time and space complexity if we use quicksort?
  • 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 the correctness of the two-pointers approach.
  • In all the above approaches, do we need to handle the case for the 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 practice

Enjoy learning, Enjoy coding, Enjoy algorithms!

We'd love to hear from you

More content from EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!