Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Flipkart, Hike, Morgan Stanley
Key takeaway
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.
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 message below. Otherwise, no problem, this is an opportunity to learn a new pattern in problem-solving!
A simple idea would be to use two nested loops and check each pair (i, j) in X[]. If there exists a pair with sum equal to targetSum, we return true. Otherwise, if we didn’t find any such pair by the end of nested loops, we return false.
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
}
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?
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.
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
}
Suppose we use efficient O(nlogn) sorting algorithm heap sort and iterative binary search to search targetSum - X[i].
Can we optimize the above approach and find a different method to search 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.
We run a loop while l < r.
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
}
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.
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.
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
}
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).
Important Note: We recommend learners transform the above pseudo-codes into a favourite programming language (C, C++, Java, Python, etc.) and verify all the test cases. Enjoy programming!
Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.