Interview Question: The Two­Sum Problem (Good Pair)

Difficulty: Medium

Asked in : Google, Facebook, Amazon

Understanding the problem

Problem Statement:

Given an array A and a integer B. A pair(i , j) in the array is a good pair if i!=j and (A[i]+A[j]==B). Check if any good pair exist or not.

For example,

Input:- A=[1, 2,3,4] and B= 7, Return 1

Input:-A = [1,2,4] and B = 4, Return 0

Possible follow-up questions to ask the interviewer :

• Can we modify the array? Yes thats fine.
• Do we know something about the range of numbers in the array? No they can be arbitrary integers.
• Are the array elements necessarily positive ? No they can be positive, negative or zero.
• Do we know something about the value of B relative to n or the numbers in the array? No, the pair should consist of two different array elements.
• Can the array contain duplicates? Surely that’s a possibility.
• Is the array necessarily in the sorted order? No that’s not guaranteed.
• What about the integer overflow? For simplicity don’t worry about this.

Designing efficient solutions

We are discussing four ways to solve this problem :

1. Brute force Approach: Using two loops
2. Using a Hash Table
3. Sorting and Binary Searc
4. Sorting and two Pointer approach

Option 1: Brute force

One option is just to try all the pairs in the array and see if any of the them adds up to number B

public int solve(int[] A, int B) {
int n=A.length;
int i, j;
for(i=0;i<n;i++){
for(j=i+1;j<n; j++){
if((i!=j)&&(A[i]+A[j]==B)){
return 1;
}
}
}
return 0;
}

Complexity Analysis

Time Complexity:O(n²) & Space Complexity:O(1) Can we improve the time complexity? Let’s try to think about it.

Option 2: Hashing

Another option is to create a hash table of all the elements in the array.You can then scan over the array and check, for each element A[i], whether there’s another element A[j] in the array where A[j] = B- A[i]. Make sure their solution correctly handles the case where there are duplicated elements in the array and doesn’t accidentally let you pair an element with itself.

Solution Steps

1. Take a Hash Table H of size O(n)
2. Run a loop and scan over the array A[] for each A[i]. Check if B-A[i] is present in the hash table or not.

• If yes, we have found the pair and return true.
• If no, then insert A[i] into the Hash table

3. If you didn’t find such a pair by end of the loop then return false.

public int solve(int[] A, int B) {
int n=A.length;
int i;
HashSet<Integer> values=new HashSet<Integer>();
for(i=0;i<n;i++){
if(values.contains(B-A[i]))
return 1;
values.add(A[i]);
}
return 0;
}

Complexity Analysis

This solution runs in expected time O(n) because n insertions and n lookups in a hash table takes expected time O(n).

Time Complexity:O(n) & Space Complexity:O(n)

Option 3: Sorting and Binary Search

The idea of binary search works perfectly in the case of the sorted array. We can sort the A[] and for each value A[i], search whether there is another value B-A[i] present in the array or not. Binary search performs searching in O(logn) which could help us to improve the time complexity.

Solution Steps

• Sort the array A[] in increasing order
• For each element A[i], use binary search to look for B-A[i].
• If there exists a value B-A[i] in the array A, then return true.
• If you didn’t find such a pair in the whole array , then return false.

public int solve(int[] A, int B) {
int n=A.length;
int i;
Arrays.sort(A);
for(i=0;i<n;i++){
int mid=Arrays.binarySearch(A,B-A[i]);
if (mid >= 0) { // Found it!
/* If this points at us, then the pair exists only if there is another copy of the element. Look ahead of us and behind us.*/
if (mid != i || (i > 0 && A[i-1] == A[i]) || (i<n-1 && A[i+1] == A[i])) {
return 1;
}
}
}
return 0;
}

Complexity Analysis

Time Complexity = Time complexity of sorting + n. Time complexity of Binary Search = O(nlogn) + n. O(logn) = O(nlogn)

Space Complexity = Space Complexity of sorting + Space complexity of the binary search (Iterative Implementation)

If merge sort ,Space Complexity = O(n) + O(1) = O(n)

If Heap Sort, Space Complexity = O(1) + O(1) = O(1)

Option 4: Sorting and Walking Inward( two Pointer approach)

A fourth option is to sort the array, then walk two pointers inward from the ends of the array, at each point looking at their sum. If it’s exactly B, then we’re done. If it exceeds B, then any sum using the larger element is too large, so we walk that pointer inwards. If it’s less than B, then any sum using the lower element is too small, so we walk that pointer inwards.

Solution Steps

1. Sort the array A[] in increasing order
2. Initialize two index variables in the sorted array A[].

• left pointer: i = 0
• right pointer : j = n-1

3) Run a loop while i< j.

• If (A[i] + A[j] == B) then return true
• if( A[i] + A[j] < B) then increment i by 1
• if( A[i] + A[j] > B) then decrement j by 1

4) If didn’t find such a pair in the whole array — return false.

public int solve(int[] A, int B) {
int n=A.length;
Arrays.sort(A);
int i=0,j=n-1;
while(i<j){
int sum=A[i]+A[j];
if (sum==B) {
return 1;
}
else if(sum<B){
i=i+1;

}else{
j=j-1;
}
}
return 0;
}

Complexity Analysis

Suppose we are using Heap Sort or merge sort.

Time Complexity = Time complexity of sorting + Time complexity of two pointer approach (while loop) = O (n log n) + O(n) = O (n log n)

If merge sort, Space Complexity = O(n)

If Heap Sort, Space Complexity = O(1)