Find Pair of Elements in an Array whose Sum is Equal to given number. Given an array of n integers and a number x, We have to write a code to find a pair of elements(a,b) in an array whose sum is equal to a given number x.
This is another important question asked in a technical interview.
Find Pair of Elements in an Array whose Sum is Equal to a given number
Let’s discuss the different approaches for solving this problem.
Method 1 – Brute Force Approach
The easiest way to find pair of elements in an array is by using two for loops.In this approach, we take one number from an array and loop through the array to check if the sum of two number is equal to the input number.
The time complexity of this approach is O(n2).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public class PairOfElements { public static void printPair(int arr[], int k) { int len = arr.length; //Traverse an array - Outer loop to pick one element in each traversal for (int i = 0; i < len; i++) { //Inner loop for checking the sum for (int j = i + 1; j < len; j++) { //If sum is equal to the given number if (arr[i] + arr[j] == k) { System.out.println("pair - (" + arr[i] + "," + arr[j] + ")"); } } } } public static void main(String[] args) { int arr[] = {4, 7, 6, 9, 1, 3, 2}; printPair(arr, 8); } } / * Output */ pair - (7,1) pair - (6,2) |
It is the simplest approach to find pair of elements in an array. This approach can work both for sorted and unsorted arrays. The only disadvantage with this approach is their time complexity.
Method 2 – Time complexity O(nlogn) :
Algorithm to Find Pair of Elements in an Array whose Sum is Equal to a given number
1. Take two indexes and initialize with the first and last index of an array. So that we can start from both the ends.
|
1 2 |
first = 0; // Assign to zeroth element of an array last = arr_size -1; // Assign last element of an array\ |
2. Run a loop and check the condition first < last.
|
1 2 3 |
If (arr[first] + arr[last] == num) then print numbers and break Else if( arr[first] + arr[last] < num ) then first++ Else if( arr[first] + arr[last] > num) then last-- |
The time complexity of this approach is O(nlogn). This method works only with sorted arrays. If the array is not sorted then sort it first in ascending order.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public class PairOfElements { public static void printPair(int arr[], int k) { int len = arr.length; int left = 0; int right = len - 1; //Traverse an array for (int i = 0; i < len; i++) { //If sum is find then print them if (arr[left] + arr[right] == k) { System.out.println("pair - (" + arr[left] + "," + arr[right] + ")"); left++; right--; } else if ((arr[left] + arr[right]) < k) { left++; } else { right--; } } } public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; printPair(arr, 8); } } /** Output **/ pair - (2,6) pair - (3,5) pair - (4,4) pair - (5,3) pair - (6,2) |
Method 3 – Time complexity O(n)
Let’s try to solve this problem in O(n). In this approach, we use HashMap to solve this problem.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.HashMap; public class PairOfElements { public static void printPair(int arr[], int k) { int len = arr.length; //HashMap declaration HashMap<Integer, Integer> arrMap = new HashMap<>(); //Traverse an array and create a Map for (int i = 0; i < len; i++) { arrMap.put(arr[i], i); } int key; for (int i = 0; i < len; i++) { //check k-arr[i] is set key = k - arr[i]; if (key > 0 && arrMap.containsKey(key)) { System.out.println("pair - (" + arr[i] + "," + arr[arrMap.get(key)] + ")"); } } } public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; printPair(arr, 8); } } /**** Output ****/ pair - (2,6) pair - (3,5) pair - (4,4) pair - (5,3) pair - (6,2) |
