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.
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.
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.
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.
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;
}
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
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 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;
}
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
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).
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 didn’t find such a pair in the whole array, we return false.
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;
}
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
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)
{
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
}
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;
}
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
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;
}
}
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).
Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!