Find the closest pair to a given sum in two sorted arrays
Given two sorted arrays, find a pair whose sum is closest to a given sum where the pair consists of elements from each array.
For example,
Input:
first[] = { 1, 8, 10, 12 }
second[] = { 2, 4, 9, 15 }
target = 11
Output: The closest pair is [1, 9]
Input:
first[] = { 10, 12, 15, 18, 20 }
second[] = { 1, 4, 6, 8 }
target = 22
Output: The closest pair is [18, 4]
first[] = { 1, 8, 10, 12 }
second[] = { 2, 4, 9, 15 }
target = 11
Output: The closest pair is [1, 9]
Input:
first[] = { 10, 12, 15, 18, 20 }
second[] = { 1, 4, 6, 8 }
target = 22
Output: The closest pair is [18, 4]
1. Brute-Force Approach
A simple solution is to consider all pairs and keep track of the pair closest to the given sum. This approach is demonstrated below in C, Java, and Python:
C
|
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 44 45 |
#include <stdio.h> #include <stdlib.h> // Function to find the closest pair to `target` in given sorted arrays // `first` and `second` void findClosestPair(int first[], int second[], int m, int n, int target) { // base case if (m == 0 || n == 0) { return; } // `x` and `y` points to the indexes of the closest pair found so far int x = 0, y = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // update the closest pair if the current pair `(i, j)` is more // closer to `target` if (abs(first[i] + second[j] - target) < abs(first[x] + second[y] - target)) { x = i; y = j; } } } printf("The closest pair is [%d, %d]", first[x], second[y]); } int main(void) { int first[] = { 1, 8, 10, 12 }; int second[] = { 2, 4, 9, 15 }; int target = 11; int m = sizeof(first) / sizeof(first[0]); int n = sizeof(second) / sizeof(second[0]); findClosestPair(first, second, m, n, target); return 0; } |
Output:
The closest pair is [1, 9]
Java
|
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 |
class Main { // Function to find the closest pair to `target` in given sorted arrays // `first` and `second` private static void findClosestPair(int[] first, int[] second, int target) { // base case if (first.length == 0 || second.length == 0) { return; } // `x` and `y` points to the indexes of the closest pair found so far int x = 0, y = 0; for (int i = 0; i < first.length; i++) { for (int j = 0; j < second.length; j++) { // update the closest pair if the current pair `(i, j)` // is more closer to `target` if (Math.abs(first[i] + second[j] - target) < Math.abs(first[x] + second[y] - target)) { x = i; y = j; } } } System.out.printf("The closest pair is [%d, %d]", first[x], second[y]); } public static void main(String[] args) { int[] first = { 1, 8, 10, 12 }; int[] second = { 2, 4, 9, 15 }; int target = 11; findClosestPair(first, second, target); } } |
Output:
The closest pair is [1, 9]
Python
|
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 |
# Function to find the closest pair to `target` in given sorted lists `first` and `second` def findClosestPair(first, second, target): # base case if not len(first) or not len(second): return () # `x` and `y` points to the indexes of the closest pair found so far x = y = 0 for i in range(len(first)): for j in range(len(second)): # update the closest pair if the current pair `(i, j)` # is more closer to `target` if abs(first[i] + second[j] - target) < abs(first[x] + second[y] - target): x = i y = j return first[x], second[y] if __name__ == '__main__': first = [1, 8, 10, 12] second = [2, 4, 9, 15] target = 11 pair = findClosestPair(first, second, target) print("The closest pair is", pair) |
Output:
The closest pair is (1, 9)
The time complexity of this approach is O(n2) and doesn’t require any extra space, where n is the size of the input.
2. Two-pointer Approach
We can easily solve the problem by maintaining two pointers, i and j, and keeping the search space first[i…] and second[…j]. The first pointer, i, initially points at the beginning of the first array, first, and the second pointer j initially points at the end of the second array, second.
At each iteration of the loop, process the elements present at index i and j and update the closest pair to the current pair (i, j) if the absolute value of (first[i] + second[j] - target) is minimum among all pairs processed.
- If the sum of the current pair
(i, j)is less thantarget, incrementias an element at indexi+1has more value than the element at indexi. - If the sum of the current pair
(i, j)is more thantarget, decrementjas an element at indexj-1has less value than the element at indexj.
The loop continues if i is less than the first array’s size, and j is more than index 0. This approach is demonstrated below in C, Java, and Python:
C
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <stdio.h> #include <stdlib.h> // Function to find the closest pair to `target` in given sorted arrays // `first` and `second` void findClosestPair(int first[], int second[], int m, int n, int target) { // base case if (m == 0 || n == 0) { return; } // `x` and `y` points to the indexes of the closest pair found so far int x = 0; // `x` initially points at the beginning of the first array int y = n - 1; // `y` initially points at the end of the second array // `i` initially points at the beginning of the first array // `j` initially points at the end of the second array for (int i = 0, j = n - 1; i < m && j >= 0;) { // maintain a search space `first[i…]` and `second[…j]` // update the closest pair found so far if the current pair `(i, j)` // is closer to `target` if (abs(first[i] + second[j] - target) < abs(first[x] + second[y] - target)) { x = i; y = j; } // if the sum of the current pair `(i, j)` is less than the given sum, // increment `i` (as an element at index `i+1` has more value than the // element at index `i`) if (first[i] + second[j] < target) { i++; } // if the sum of the current pair `(i, j)` is more than the given sum, // decrement `j` (as an element at index `j-1` has less value than the // element at index `j`) else if (first[i] + second[j] > target) { j--; } // otherwise, increment `i` and decrement `j` else { i++; j--; } } printf("The closest pair is [%d, %d]", first[x], second[y]); } int main(void) { int first[] = { 1, 8, 10, 12 }; int second[] = { 2, 4, 9, 15 }; int target = 11; int m = sizeof(first) / sizeof(first[0]); int n = sizeof(second) / sizeof(second[0]); findClosestPair(first, second, m, n, target); return 0; } |
Output:
The closest pair is [1, 9]
Java
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Main { // Function to find the closest pair to `target` in given sorted arrays // `first` and `second` private static void findClosestPair(int[] first, int[] second, int target) { // base case if (first.length == 0 || second.length == 0) { return; } /* `x` and `y` points to the indexes of the closest pair found so far */ // `x` initially points at the beginning of the first array int x = 0; // `y` initially points at the end of the second array int y = second.length - 1; // `i` initially points at the beginning of the first array // `j` initially points at the end of the second array for (int i = 0, j = second.length - 1; i < first.length && j >= 0; ) { // maintain a search space `first[i…]` and `second[…j]` // update the closest pair found so far if the current pair `(i, j)` // is closer to `target` if (Math.abs(first[i] + second[j] - target) < Math.abs(first[x] + second[y] - target)) { x = i; y = j; } // if the sum of the current pair `(i, j)` is less than the given sum, // increment `i` (as an element at index `i+1` has more value than the // element at index `i`) if (first[i] + second[j] < target) { i++; } // if the sum of the current pair `(i, j)` is more than the given sum, // decrement `j` (as an element at index `j-1` has less value than the // element at index `j`) else if (first[i] + second[j] > target) { j--; } // otherwise, increment `i` and decrement `j` else { i++; j--; } } System.out.printf("The closest pair is [%d, %d]", first[x], second[y]); } public static void main(String[] args) { int[] first = { 1, 8, 10, 12 }; int[] second = { 2, 4, 9, 15 }; int target = 11; findClosestPair(first, second, target); } } |
Output:
The closest pair is [1, 9]
Python
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# Function to find the closest pair to `target` in given sorted lists `first` and `second` def findClosestPair(first, second, target): # base case if not len(first) or not len(second): return () # `x` and `y` points to the indexes of the closest pair found so far x = 0 # `x` initially points at the beginning of the first array y = len(second) - 1 # `y` initially points at the end of the second array # `i` initially points to the start of array `first` i = 0 # `j` initially points at the end of the second array j = len(second) - 1 while i < len(first) and j >= 0: # maintain a search space `first[i…]` and `second[…j]` # update the closest pair found so far if the current pair `(i, j)` # is closer to `target` if abs(first[i] + second[j] - target) < abs(first[x] + second[y] - target): x = i y = j # if the sum of the current pair `(i, j)` is less than the given sum, # increment `i` (as an element at index `i+1` has more value than the # element at index `i`) if first[i] + second[j] < target: i = i + 1 # if the sum of the current pair `(i, j)` is more than the given sum, # decrement `j` (as an element at index `j-1` has less value than the # element at index `j`) elif first[i] + second[j] > target: j = j - 1 # otherwise, increment `i` and decrement `j` else: i = i + 1 j = j - 1 return first[x], second[y] if __name__ == '__main__': first = [1, 8, 10, 12] second = [2, 4, 9, 15] target = 11 pair = findClosestPair(first, second, target) print("The closest pair is", pair) |
Output:
The closest pair is (1, 9)
The time complexity of the above solution is O(n) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)