Find all the Pairs in Integer Array whose sum is equal to a given number.

Problem:

As heading says, The problem is to find all the Pairs in Integer Array whose sum is equal to a given number. for example if integer arrays is {4,5,6,2,1} and given number is 9 then answer should be (4,5).

This is again an interesting problem to solve and have many correct solutions but interview would look for the most efficient one and thought process behind it.

Brute Method:

1. Loop through the list twice; second loop will start from first loop index +1.
2. Compare the sum of inner index element and outer index element with given sum value.
3. And print the pair if match is found.

1:  public static void findPairs(){  
2:            for (int i=0;i<intList.length;i++) {  
3:                 for (int j=i+1;j<intList.length;j++) {  
4:                      if(sum.equals(intList[i]+intList[j])){  
5:                           System.out.printf("(%d, %d) %n",intList[j],intList[i]);  
6:                      }  
7:                 }  
8:            }  
9:            System.out.println("");  
10:       }  

Now this solution will give you exact result but time complexity of this method is O(N²).

To reduce the time complexity, we can add up some space complexity and reach to the solution.
One way of doing this would be to use HashSet.

1. Loop through the list.
2. Search the target value (given number - element from the list) in a given Set.
3. If set contains the target value; print it pair (element from the list and target) otherwise add the target to the set.

1:       public static void findPairsWithSet(){  
2:            Set<Integer> set = new HashSet<Integer>(intList.length);  
3:            for (int i=0;i<intList.length;i++) {  
4:                 Integer target = sum - intList[i];  
5:                 if(set.contains(target)){  
6:                      System.out.printf("(%d, %d) %n",intList[i],target);  
7:                 } else{  
8:                      set.add(intList[i]);  
9:                 }  
10:            }  
11:            System.out.println("");  
12:       }  

This reduces the time complexity to O(N) because contains method's complexity for a Set is O(1). But you will need extra space to save the Set so it will increase the space complexity of this method to O(N) which is bad in case of very large integer array.

Best solution would be to Sort the array and maintain the 2 pointers in the array.

1. Sort the array in ascending order.
2. Maintain 2 pointers, one at beginning and second one at the tail.
3. Keep increasing the first pointer and decreasing the tail pointer if a match is found.
4. If addition of first index element and second index element is less than given number; increase the first pointer.
5. Similarly if addition of  first index element and second index element is greater than given number; decrease the second pointer
6. Keep doing Step 3,4,5 until both pointer cross each other.

1:       public static void findPairsWithSorting(){  
2:            Arrays.sort(intList);  
3:            int left=0;  
4:            int right = intList.length -1;  
5:            while(left < right){  
6:                 Integer addition = intList[left] + intList[right];  
7:                 if(addition.equals(sum)){  
8:                      System.out.printf("(%d, %d) %n",intList[left],intList[right]);  
9:                      left++;  
10:                      right--;  
11:                 } else if(addition.compareTo(sum) <0){  
12:                      left++;  
13:                 } else {  
14:                      right-- ;  
15:                 }  
16:            }  
17:       }  

This is the best solution in my opinion because first of Arrays.sort uses two pivot quick sort algorithm, so complexity of this method would be ~O(N).

Try out this methods with your examples and please do let me know in comments below if there is an even better solution to this problem.