**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.

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!

- 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 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?

**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)

**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**

- We sort the input array in increasing order.
- Now we initialize two pointers in the sorted array, left pointer l = 0, and right pointer r = n-1
- We run a loop while l < r
- If (X[l] + X[r] == targetSum), then return we true.
- if( X[l] + X[r] < targetSum), then we increment l by 1.
- 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 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.

**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!

- 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?

- 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)

- Trapping rain-water
- Move zeroes to an end
- Container With Most Water
- Remove duplicates from sorted array
- Whether an array is a subset of another array
- Merge two sorted arrays
- Find the intersection of two sorted array
- Count the number of possible triangles
- Find four elements that sum to a given value
- Triplet in the array whose sum is equal to the given value.

**Enjoy learning, Enjoy coding, Enjoy algorithms!**

Find the row with the maximum number of 1s

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. This is an excellent matrix problem that can be solved in linear time complexity. The best part is — we are using the sorted order property and nested loops to improve the solution over the binary search approach.

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