Count pairs with given sum best solution [How to Find all Pairs in Array of Integers Whose sum is Equal to a Given Number]

Find a pair of elements from an array whose sum equals a given number

Coding skill is very important, being a programmer we have to be in practice so that when ever we came across with any problem we can design and build best possible logic for given problem statements.

This blog will cover the most important question "finding a pair of elements from an array whose sum equals to given number." or "Count pairs with given sum" or "Print all pairs with given sum."

Array Interview question

Approach #1  Find Pair with given Sum in the Array

We can use hash table to solve this problem.
a. Initialise a set
b. for each element in array check if it present in the set.

      > if it present in set then element and (sum - element) are the pairs.

      > if not present in set then add (sum - element) into the set.

Code in java to print all the pair whose sum is equal to given number: 

class Template{

        public static List<List<Integer>> findSum(Integer array[], int sum) {

Set<Integer> set = new HashSet<Integer>();

List<List<Integer>> pairs = new ArrayList<Integer>();

               for (Integer element : array) {

if (set.contains(element)) {

List<Integer> pair = new ArrayList<Integer>();

pair.add(element);

pair.add((sum - element));

pairs.add(pair);

} else {

set.add(sum - element);

}

}

return pairs;

            }

         public static void main(String args[]){

               int sum  = 10;
               Integer array[] = new Integer[] {2,4,6,1,3,7,8,2,1,9, 15, -5};

               List<List<Integer>> pairs = findSum(array, sum);

               System.out.println(pairs);

         }

}

Output : [[6, 4], [7, 3], [8, 2], [9, 1], [-5, 15]]

Time Complexity : O(n) , this approach will be solved in O(n)

Approach #2 Find Pair with given Sum in the Array

This is another approach in which we apply our logic after sorting array into ascending order.
Let's see steps for the same.

Step 1 :  Sort the given array in ascending order.
Step 2 :  Initialize two index variables to find the pair elements in the sorted array.
          (a) Initialize first to the leftmost index: left = 0
          (b) Initialize second  the rightmost index:  right = array_size - 1
Step 3 : Loop while left < right.
          (a) If (Array[left] + Array[right] == sum)  then these are the right pair store it into list.
          (b) Else if( A[left] + A[right] <  sum )  then left++
          (c) Else right-- 
Step 4 : Return the list.

Print all pairs with given sum in java

public class PairTemplate {

public static List<List<Integer>> findPairSum(Integer array[], int sum) {

List<List<Integer>> pairs = new ArrayList<>();

Arrays.sort(array); // sort the element.

int left = 0;

int right = array.length - 1;

while (left < right) {

if (array[left] + array[right] == sum) {

List<Integer> pair = new ArrayList<Integer>();

pair.add(array[left]);

pair.add(array[right]);

pairs.add(pair); // store the pair into the list

left++;

right--;

} else if (array[left] + array[right] < sum) {

left++;

} else {

right--;

}

}

return pairs;

}

public static void main(String[] args) {

int sum =10;

Integer array[] = new Integer[] {2,4,6,1,3,7,8,2,1,9, 15, -5};

List<List<Integer>> pairs = findPairSum(array, sum);

System.out.println(pairs);

}

}

Output : [[-5, 15], [1, 9], [2, 8], [3, 7], [4, 6]]

Time Complexity :
Time Complexity will be depend on what sorting algorithm we use.
(a) If we use Merge Sort or Heap Sort then Θ(𝑛log𝑛) in worst case.
(b) If we use Quick Sort then O(n^2) in worst case.

Click here to learn Why java takes 2 byte to store a character.

Click here to learn Supplementary characters in the java