Find all pairs of elements from an array whose sum is equal to given number

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Problem :

Given a  array,we need to find all pairs whose sum is equal to number X.
For example:

Solution :

Solution 1:

You can check each and every pair of numbers and find the sum equals to  X.
Java code:

 Solution 2:

  • Sort the array
  • We will maintain two indexes one at beginning (l=0) and one at end (r=n-1)
  • iterate until l <  r
  • Check if arr[l] + arr[r] is equal to X
  • if Yes, then print the pair and do l++, r–
  • If arr[l] + arr[r] is less than X, this means if we want to find sum close to X, do r–
  • If arr[l] + arr[r] is greater than X,this means if we want to find sum close to X , do l++
Java code:

Time complexity : O(NLogN)

Solution 3:

Using Hashing

  • Put array element in HashMap with element as key and its index as value.
  • Iterate over array arr[]
  • Check for arr[i],  if X-arr[i] is present in HashMap.
  • If yes, we have found the pair and print it.
Java code:

Time complexity : O(NLogN) Space complexity : O(N)

Java program to find all pairs whose sum is equal to given number:

When you run above program, you will get below output:

Add Comment