Find pairs with given sum in a sorted array.
Given an array A of size N. Write a code to find all pairs in the array that sum to a number equal to K. If no such pair exists then output will be –1.
NOTE – The array elements are distinct and in a sorted order.
For example –
Input :
arr[] = {1, 2, 3, 4, 5, 6, 7};
sum = 9
Output:
Pairs with given sum 9 is
Pair (2 , 7 )
Pair (3 , 6 )
Pair (4 , 5 )
Find Pairs with Given Sum in a Sorted Array
How to Find Pairs with Given Sum in Array
i) To solve this problem, let’s take two indexes low and high and assign a value zero and array length -1.
low = 0, high = arr.length-1
ii) Traverse an array from both the ends and increment the value of low and high based on whether the sum of arr[low] + arr[high] is greater or less than the given sum.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
low = 0 high = length - 1; while(low < high) { if(arr[low] + arr[high] > sum) { high--; } else if (arr[low] + arr[high] < sum) { low++; } else if (arr[low] + arr[high] == sum) { print value of arr[low] and arr[high] low++; high--; } } |
iii) If we found the pairs with given sum then print the value.
The time complexity of this approach is O(n).
Find Pairs with Given Sum in a Sorted Array – Java Code
We have discussed how we can solve this problem in O(n) time complexity.
Let’s write a java code print all the pairs with given sum in an array.
|
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 |
/** * Find Pairs with Given Sum in an Array */ public class PairSum { public static void main(String[] args) { //Sorted array with distinct elements int arr[] = {1, 2, 3, 4, 5, 6, 7}; int sum = 9; //Two indexes low and high int low = 0; int high = arr.length - 1; while(low < high) { /* if sum of arr[low] + arr[high] is greater than the value of sum then decrement the value of high. */ if((arr[low] + arr[high]) > sum) { high--; } else if ((arr[low] + arr[high]) < sum) { low++; } else if((arr[low] + arr[high]) == sum) { System.out.println(" Pair (" + arr[low] + " , " + arr[high] + " )"); low++; high--; } } } } |
