Check for pair in an array with a given sum

Check for pair in an array with a given sum - Interview Problem

Difficulty Level : Medium

Asked in : Google, Facebook, Amazon

Understanding the problem

Problem Description: Given an array of n integers and given a number K, determines whether there is a pair of elements in the array that sums to exactly K.

For example :

Input : A[] = [-5, 1, -40, 20, 6, 8, 7 ], K=15

Output: true ( 7, 8 and -5, 20 are the pairs with sum 15)

Input : A[] = [-5, 4, -2, 16, 8, 9], K=15

Output: false (There is no pair of elements whose sum is equal to 15)

Possible follow-up questions to ask the interviewer :

Do we know something about the range of the numbers in the array? Ans: No, they can be arbitrary integers.
Are the array elements necessarily positive? Ans: No, they can be positive, negative, or zero.
Do we know anything about the value of K relative to the numbers in the array? Ans: No, it can be arbitrary.
Can we consider pairs of an element and itself? Ans: No, the pair should consist of two different array elements.
Can the array contain duplicates? Ans: Sure, that's a possibility.

Designing efficient solutions

We are discussing four ways to solve this problem :

Brute force Approach: Using two loops
Sorting and binary search
Sorting and two Pointer approach
Using a Hash Table

1. Brute Force Approach: Using two loops

Use two loops and check A[i] + A[j] == K for each pair (i, j) in A[]. If there exists a pair with sum equals to K then return true. By end of both loops, If you didn’t find such a pair then return false.

Pseudo Code

int find_sumPair (A[], n, K)
{
  for( i = 0 to n-1 )
  {
     for(j = i+1 to n-1)
     { 
         if(A[i]+A[j] == K)
         return 1
     }
  }
return -1
}

Complexity Analysis

The total no. of comparison in worst case = Total no. of possible pairs = nC2 = n(n-1)/2 = O(n²)

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

2. 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 K-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 K-A[i].
If there exists a value K-A[i] in the array A, then return true.
If you didn’t find such a pair in the whole array , then return false.

Pseudo Code

int find_sumPair (A[], n, K)
 {
   Sort ( A, n)
   for( i = 0 to n-1 )
   { 
      x = binarySearch ( A, 0, n-1, K-A[i] )
      if ( x ) 
      return 1
   }
 return -1
 }

Complexity Analysis

Suppose we are using heap sort/merge sort and iterative binary search for the implementation.

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)

Critical Ideas to think!

What would be the time and space complexity if we use quicksort? Compare different sorting algorithms
What would be the space complexity of the recursive binary search?
Why are we searching K - A[i] for each element in array A[]?
Prepare a list of problems where you can apply the idea of sorting and binary search.

3. Sorting and two Pointer approach

Sort the array A[] then walk two pointers inward from the ends of the array, at each point looking at their sum. If it is exactly k, then we are done. If it exceeds k, then any sum using the larger element is too large, so we walk that pointer inwards. If it is less than k, then any sum using the lower element is too small, so we walk that pointer inwards.

Solution Steps

Sort the array A[] in increasing order
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] == K) then return true
if( A[i] + A[j] < K) then increment i by 1
if( A[i] + A[j] > K) then decrement j by 1

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

Solution Visualization

Pseudo Code

int find_sumPair( A[], n, K)
 { 
    Sort(A, n)
    i = 0
    j = n -1 
    while (i < j)
    {
       if(A[i] + A[j] == K)
         return 1
       else if(A[i] + A[j] < K)
         i = i+1
       else
         j = j-1
    } 
 return -1
 }

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)

Critical Ideas to think!

is this algorithm works fine if elements are repeated?
The time complexity of while loop is O(n) in the worst-case - why?
Why the idea of the two pointer approach works perfectly for a sorted array?
Prepare a list of problems where you can apply the idea of two pointer approach for the solution.

4. Using a Hash Table

Idea is to use the Hash Table to improve the time complexity because it performs searching and insertion efficiently in O(1) average.

Solution Steps

Take a Hash Table H of size O(n)
Run a loop and scan over the array A[] for each A[i]. Check if K-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.

Pseudo Code

bool checkPair(int A[], int n, int K) 
{ 
  Take Hash Table H of size O(n)
  for (i = 0 to n-1)
  { 
      int x = K - A[i]
      if (H.search(x) is true) 
          return 1
      H.insert(A[i]) 
  } 
 return -1
}

Complexity Analysis

In worst case scenario, we scan the whole array and didn't find any such pair. Time Complexity = Time complexity of inserting n elements in hash table + Time complexity of searching (K-A[i]) n times in hash table = n. O(1) + n . O(1) = O(n)

Space Complexity = Extra space of Hash Table = O(n)

Critical Ideas to think!

is this algorithm works fine if elements are repeated?
What would be the time and space complexity if we use a binary search tree in place of a hash table? Compare hash table and binary search tree
This is also a good example of problem-solving via data structure. Prepare a list of problems where we use data structures (hash table, BST, priority queue, stack, queue, etc) for the efficient solution.
Is there any other way to solve this problem? Think