Dinesh on Java

It many times asked question in the programming interview. We have an array of integers and a given number so we have to find all pair in the array whose sum is equal to a given number. Suppose we have an array {4, 2, 5, 7, -1} and given number 6 so these pair will be (4,2) and (7,-1).

• Array may contains positive or negative numbers.
• Same pair could be repeated twice, we should print it every time.
• Reverse of pair is acceptable e.g. can we print both (4,2) and (2,4) if given sum is 6.
• Array may be big in size.

Solutions
There are following three solutions available for this problem. Lets see below the three solutions.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 
 */

/**
 * @author Dinesh.Rajput
 *
 */
public class PairSumInArray {

 /**
  * @param args
  */
 public static void main(String[] args) {
  int [] array = {3,4,1,6,-1,7,5,2};
  int number = 6;
  firstSolutionON2(array, number);//This solution has O(n2) time complexity
  secondSolutionON1(array, number);//This solution has O(n) time complexity but consume extra space
  thirdSolutionONlogN(array, number);//This solution has O(NlogN)time complexity extra logN for Arrays.sort() method it using quick sort behind
 }

 private static void firstSolutionON2(int[] array, int number) {
  System.out.println("=====First Solution====");
  for(int i = 0; i < array.length ; i++){
   int first = array[i];
   for(int j = i +1 ; j < array.length; j++){
    int second = array[j];
    if(first+second == number){
     System.out.println("("+first+","+second+")");
    }
   }
  }
 }
 private static void secondSolutionON1(int[] array, int number) {
  Set<Integer> set = new HashSet<Integer>();
  System.out.println("=====Second Solution====");
  for(int a : array){
   int diff = number - a;
   if(set.contains(diff)){
    System.out.println("("+diff+","+a+")");
   }else{
    set.add(a);
   }
  }
 }
 private static void thirdSolutionONlogN(int[] array, int number) {
  Arrays.sort(array);
  int left = 0;
  int right = array.length -1 ;
  System.out.println("=====Third Solution====");
  while(left < right){
   int leftItem = array[left];
   int rightItem = array[right];
   if(leftItem+rightItem == number){
    System.out.println("("+leftItem+","+rightItem+")");
    left++;
    right--;
   }else if(leftItem+rightItem > number){
    right--;
   }else if(leftItem+rightItem < number){
    left++;
   }
  }
  
 }
}

Discussion for First Solutions
You take one number from array and then loop through array and output pairs which is equal to given sum. This solution is correct but it’s time complexity is very high, O(n^2).

Discussion for Second Solutions
What we can do here is to store all numbers in a hashtable and just check if it contains second value in a pair. How is this solution better than previous one? It would require less comparisons. Only N to iterate through array and insert values in a Set because add() and contains() both O(1) operation in hash table. So total complexity of solution would be O(N). But this solution has few constraints, first it would need additional space of order O(n) to store numbers in Hashtable or Set, so you need additional space which could be problem if array is very large (remember the question we asked before writing solution). For a large array, you need a solution which doesn’t require additional space, also known as in-place solution.

Discussion for Third Solutions
A more efficient in-place solution would be to sort the array and use two pointers to scan through array from both direction i.e. beginning and end. If sum of both the values are equal to given number then we output the pair and advance them. If the sum of two numbers is less than k then we increase the left pointer, else if the sum is greater than k we decrements the right pointer, until both pointers meet at some part of the array. The complexity of this solution would be O(NlogN) due to sorting.