Find all pairs of elements from array whose sum equals to given number K.

Find all pairs of elements from array whose sum equals to given number K OR
Count all pairs with given sum K OR
Java Program to find pairs on integer whose sum is equal to K.

---

Given an array of integers, Find all pairs of number whose sum is equal to given number K. 

You can also say, Write a Java Program to find all pairs of numbers from integer array whose sum is equal to given number K.

Let's understand what is the Input and expected Output.

Find all pairs with a given sum in array in Java

Algorithm

---

To find all pairs of elements from array whose sum equals to given number K.

There are many approach to find all pairs with given sum, we will see 2 approach below,

1. Using List.
2. Using 2 Pointers

1. Using List

In this approach, we will pick each element (p) from the array and see, is the corresponding element (q) which we get after subtracting (p) from K is present in list,  

1. If Yes, then we will print the (p) and (q) and remove (q) from the list.
2. If Not, then we will add (q) in the list.

Algorithm will be more clear when we understand it with below example.

Find all the pairs of elements whose sum is K

2. Using 2 Pointers.

Above approach requires storage, in our case we used list to store elements.
What if the question is asked in a way that you cannot used any extra memory.

Yes, In that case this approach will be helpful.

STEP 1: In this approach we will first sort our Array. 
STEP 2: Take 2 pointers P and Q.
P pointing at start of array that is at P=0 and Q pointing at end of the array that is at Q=arr.length-1;

If array[P] + arr[Q] == K,
If Yes, then we got a Pair and Print array[P] and array[Q].
As we already explored current index P and Q, Increment P++ and Decerement Q-- for next step.

If array[P] + array[Q] is < K, 
It means, we can still get the sum by incrementing our lower value pointer P++.
 
If array[P] + array[Q] is > K, 
It means, we can still get the sum by decrementing our higher value pointer Q--. 

Stop when P meets Q, that is when they both points to same index.


Algorithm will be more clear when we understand it with below example.

Print all pairs with given sum in Java

Java Program to Find all pairs of elements from array whose sum equals to given number K.

---

package javabypatel;

import java.util.ArrayList;
import java.util.List;

public class Find2NumbersWhoseSumIsKInArray {

 public static void main(String[] args) {
  int[] array = new int[]{-1,  0,  2,  5,  -4,  5,  10,  6};

  System.out.println("\n---------Solution 1---------");
  List<Pair> listOfPair = getAllPairsWhoseSumIsKUsingList(array, 5);

  for (Pair pair : listOfPair) {
   System.out.print(pair.getA() + " " + pair.getB() + "\n");
  }

  System.out.println("\n---------Solution 2---------");
  List<Pair> listOfPair1 = getAllPairsWhoseSumIsKUsing2Pointers(array, 5);
  for (Pair pair : listOfPair1) {
   System.out.print(pair.getA() + " " + pair.getB() + "\n");
  }
 }

 //Time Complexity O(n), Space Complexity O(n) 
 private static List<Pair> getAllPairsWhoseSumIsKUsingList(int arr[], int k){
  if(arr==null || arr.length<1)return null;

  List<Pair> listOfPair = new ArrayList<Pair>();
  List<Integer> list = new ArrayList<Integer>();

  for (int i = 0; i < arr.length; i++) {
   int temp = k - arr[i];
   if(list.contains(temp)){
    listOfPair.add(new Pair(arr[i], temp));
    
    //Remove the element from the list, otherwise we will end up printing the pairs twice.
    list.remove(list.indexOf(temp));
   }else{
    list.add(arr[i]);
   }
  }
  return listOfPair;
 }

 
 private static List<Pair> getAllPairsWhoseSumIsKUsing2Pointers(int arr[], int k){
  if(arr==null || arr.length<1)return null;

  //First Sort the array
  System.out.println("\nBefore Sorting :");
  printArray(arr); 
  quickSort(arr, 0, arr.length-1); //Or you can use Arrays.sort(arr);
  System.out.println("After Sorting :");
  printArray(arr);
  System.out.println("\n");

  List<Pair> listOfPair = new ArrayList<Pair>();
  int i=0;
  int j=arr.length-1;
  while(i<=j){
   if(arr[i]+arr[j]==k){
    listOfPair.add(new Pair(arr[i], arr[j]));
    i++;
    j--;
   }else if(arr[i]+arr[j]>k){
    j--;
   }else{
    i++;
   }
  }
  return listOfPair;
 }

 private static void quickSort(int[] array, int lowerIndex, int higherIndex) {
  int i = lowerIndex;
  int j = higherIndex;
  int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
  while (i <= j) {
   while (array[i] < pivot) {
    i++;
   }
   while (array[j] > pivot) {
    j--;
   }
   if (i <= j) {
    int tmp = array[i];
    array[i]=array[j];
    array[j]=tmp;
    i++;
    j--;
   }
  }
  if (lowerIndex < j)
   quickSort(array, lowerIndex, j);
  if (i < higherIndex)
   quickSort(array, i, higherIndex);
 }

 private static void printArray(int arr[]){
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
  System.out.println();
 }
}

Pair.java

package javabypatel;
 
public class Pair {
 
 private int a;
 private int b;
 
 public Pair(int a, int b) {
  this.a = a;
  this.b = b;
 }
 public int getA() {
  return a;
 }
 public void setA(int a) {
  this.a = a;
 }
 public int getB() {
  return b;
 }
 public void setB(int b) {
  this.b = b;
 }
 
}

You may also like to see

---

Compress a given string in-place and with constant extra space.

Check whether a given string is an interleaving of String 1 and String 2.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

Serialize and Deserialize a Binary Tree

Advanced Multithreading Interview Questions In Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.