Given two arrays arr1[] and arr2[], and a positive integer x, find a pair ( arr1[i] , arr2[j] ) such that the absolute difference | arr1[i] + arr2[j] - x | is minimized.
Example:
Input: arr1[] = [1, 4, 5, 7], arr2[] = [10, 20, 30, 40], x = 32
Output: [1, 30]
Input: arr1[] = [1, 4, 5, 7], arr2[] = [10, 20, 30, 40], x = 50
Output: [7, 40]
Try it on GfG Practice
Table of Content
[Naive Approach] Using Nested Loops - O(n × m) Time and O(1) Space
The naive approach is to check all possible pairs formed by taking one element from arr1[] and one from arr2[]. For each pair we will compute the value |arr1[i] + arr2[j] − x| and keep track of the pair that gives the minimum difference.
[Better Approach] Using Binary Search - O(n × log m) Time and O(1) Space
Since both arrays are sorted, for any element arr1[i], the element in arr2[] that gives a sum closest to x must be near x − arr1[i]. Thus, for each element of arr1[] binary search is used on arr2[] to find the closest value to the target and update the minimum difference accordingly.
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
// Helper function to perform binary search on arr2
// Returns the index of the element closest to 'target'
int findClosestIndex(vector<int> &arr2, int target)
{
int left = 0, right = arr2.size() - 1;
int closestIdx = -1;
int minDiff = INT_MAX;
while (left <= right)
{
int mid = left + (right - left) / 2;
int diff = abs(arr2[mid] - target);
if (diff < minDiff)
{
minDiff = diff;
closestIdx = mid;
}
if (arr2[mid] == target)
return mid;
else if (arr2[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return closestIdx;
}
vector<int> findClosestPair(vector<int> &arr1, vector<int> &arr2, int x)
{
int n = arr1.size();
int m = arr2.size();
int diff = INT_MAX;
vector<int> result(2);
// Traverse each element in arr1 and find its closest counterpart in arr2
for (int i = 0; i < n; i++)
{
int target = x - arr1[i];
// Find the index of the closest element to target in arr2
int idx = findClosestIndex(arr2, target);
// Check if this pair gives a closer sum to x
if (idx != -1 && abs(arr1[i] + arr2[idx] - x) < diff)
{
diff = abs(arr1[i] + arr2[idx] - x);
result[0] = arr1[i];
result[1] = arr2[idx];
}
}
return result;
}
int main()
{
vector<int> arr1 = {1, 4, 5, 7};
vector<int> arr2 = {10, 20, 30, 40};
int x = 38;
// Find the closest pair
vector<int> closest = findClosestPair(arr1, arr2, x);
cout << "[" << closest[0] << ", " << closest[1] << "]" << endl;
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
class GfG {
// Helper function to perform binary search on arr2
// Returns the index of the element closest to 'target'
static int findClosestIndex(int[] arr2, int target) {
int left = 0, right = arr2.length - 1;
int closestIdx = -1;
int minDiff = Integer.MAX_VALUE;
while (left <= right) {
int mid = left + (right - left) / 2;
int diff = Math.abs(arr2[mid] - target);
if (diff < minDiff) {
minDiff = diff;
closestIdx = mid;
}
if (arr2[mid] == target)
return mid;
else if (arr2[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return closestIdx;
}
static ArrayList<Integer> findClosestPair(int[] arr1, int[] arr2, int x) {
int n = arr1.length;
int m = arr2.length;
int diff = Integer.MAX_VALUE;
ArrayList<Integer> result = new ArrayList<>(Arrays.asList(0, 0));
// Traverse each element in arr1 and find its closest counterpart in arr2
for (int i = 0; i < n; i++) {
int target = x - arr1[i];
// Find the index of the closest element to target in arr2
int idx = findClosestIndex(arr2, target);
// Check if this pair gives a closer sum to x
if (idx != -1 && Math.abs(arr1[i] + arr2[idx] - x) < diff) {
diff = Math.abs(arr1[i] + arr2[idx] - x);
result.set(0, arr1[i]);
result.set(1, arr2[idx]);
}
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 4, 5, 7};
int[] arr2 = {10, 20, 30, 40};
int x = 38;
// Find the closest pair
ArrayList<Integer> closest = findClosestPair(arr1, arr2, x);
System.out.println("[" + closest.get(0) + ", " + closest.get(1) + "]");
}
}
# Helper function to perform binary search on arr2
# Returns the index of the element closest to 'target'
def findClosestIndex(arr2, target):
left, right = 0, len(arr2) - 1
closestIdx = -1
minDiff = float('inf')
while left <= right:
mid = left + (right - left) // 2
diff = abs(arr2[mid] - target)
if diff < minDiff:
minDiff = diff
closestIdx = mid
if arr2[mid] == target:
return mid
elif arr2[mid] < target:
left = mid + 1
else:
right = mid - 1
return closestIdx
def findClosestPair(arr1, arr2, x):
n = len(arr1)
m = len(arr2)
diff = float('inf')
result = [0, 0]
# Traverse each element in arr1 and find its closest counterpart in arr2
for i in range(n):
target = x - arr1[i]
# Find the index of the closest element to target in arr2
idx = findClosestIndex(arr2, target)
# Check if this pair gives a closer sum to x
if idx != -1 and abs(arr1[i] + arr2[idx] - x) < diff:
diff = abs(arr1[i] + arr2[idx] - x)
result[0] = arr1[i]
result[1] = arr2[idx]
return result
if __name__ == "__main__":
arr1 = [1, 4, 5, 7]
arr2 = [10, 20, 30, 40]
x = 38
# Find the closest pair
closest = findClosestPair(arr1, arr2, x)
print(f"[{closest[0]}, {closest[1]}]")
using System;
using System.Collections.Generic;
class GfG
{
// Helper function to perform binary search on arr2
// Returns the index of the element closest to 'target'
static int FindClosestIndex(int[] arr2, int target)
{
int left = 0, right = arr2.Length - 1;
int closestIdx = -1;
int minDiff = int.MaxValue;
while (left <= right)
{
int mid = left + (right - left) / 2;
int diff = Math.Abs(arr2[mid] - target);
if (diff < minDiff)
{
minDiff = diff;
closestIdx = mid;
}
if (arr2[mid] == target)
return mid;
else if (arr2[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return closestIdx;
}
static List<int> findClosestPair(int[] arr1, int[] arr2, int x)
{
int n = arr1.Length;
int m = arr2.Length;
int diff = int.MaxValue;
List<int> result = new List<int> { 0, 0 };
// Traverse each element in arr1 and find its closest counterpart in arr2
for (int i = 0; i < n; i++)
{
int target = x - arr1[i];
// Find the index of the closest element to target in arr2
int idx = FindClosestIndex(arr2, target);
// Check if this pair gives a closer sum to x
if (idx != -1 && Math.Abs(arr1[i] + arr2[idx] - x) < diff)
{
diff = Math.Abs(arr1[i] + arr2[idx] - x);
result[0] = arr1[i];
result[1] = arr2[idx];
}
}
return result;
}
static void Main()
{
int[] arr1 = { 1, 4, 5, 7 };
int[] arr2 = { 10, 20, 30, 40 };
int x = 38;
// Find the closest pair
List<int> closest = findClosestPair(arr1, arr2, x);
Console.WriteLine($"[{closest[0]}, {closest[1]}]");
}
}
// Helper function to perform binary search on arr2
// Returns the index of the element closest to 'target'
function findClosestIndex(arr2, target) {
let left = 0, right = arr2.length - 1;
let closestIdx = -1;
let minDiff = Number.MAX_SAFE_INTEGER;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
let diff = Math.abs(arr2[mid] - target);
if (diff < minDiff) {
minDiff = diff;
closestIdx = mid;
}
if (arr2[mid] === target)
return mid;
else if (arr2[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return closestIdx;
}
function findClosestPair(arr1, arr2, x) {
let n = arr1.length;
let m = arr2.length;
let diff = Number.MAX_SAFE_INTEGER;
let result = [0, 0];
// Traverse each element in arr1 and find its closest counterpart in arr2
for (let i = 0; i < n; i++) {
let target = x - arr1[i];
// Find the index of the closest element to target in arr2
let idx = findClosestIndex(arr2, target);
// Check if this pair gives a closer sum to x
if (idx !== -1 && Math.abs(arr1[i] + arr2[idx] - x) < diff) {
diff = Math.abs(arr1[i] + arr2[idx] - x);
result[0] = arr1[i];
result[1] = arr2[idx];
}
}
return result;
}
// Driver Code
let arr1 = [1, 4, 5, 7];
let arr2 = [10, 20, 30, 40];
let x = 38;
// Find the closest pair
let closest = findClosestPair(arr1, arr2, x);
console.log(`[${closest[0]}, ${closest[1]}]`);
Output
[7, 30]
[Expected Approach] - Using Two Pointer - O(n + m) Time and O(1) Space
The idea is to use the two-pointer technique, taking advantage of the fact that both arrays are sorted.
We place one pointer at the beginning of the first array and another at the end of the second array.
At each step, we compare the sum of the two elements withxand move the pointers in the direction that brings the sum closer tox, while updating the minimum difference found so far.
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
vector<int> findClosestPair(vector<int> &arr1, vector<int> &arr2, int x)
{
int n = arr1.size();
int m = arr2.size();
int l = 0, r = m - 1;
int diff = INT_MAX;
vector<int> result(2);
// Traverse both aays using two pointers
while (l < n && r >= 0)
{
int sum = arr1[l] + arr2[r];
int currDiff = abs(sum - x);
// Update result if closer pair is found
if (currDiff < diff)
{
diff = currDiff;
result[0] = arr1[l];
result[1] = arr2[r];
}
// Move pointers to bring sum closer to x
if (sum > x)
r--;
else
l++;
}
return result;
}
int main()
{
vector<int> arr1 = {1, 4, 5, 7};
vector<int> arr2 = {10, 20, 30, 40};
int x = 38;
vector<int> closest = findClosestPair(arr1, arr2, x);
cout << "[" << closest[0] << ", " << closest[1] << "]";
return 0;
}
import java.util.ArrayList;
class GfG {
public static ArrayList<Integer> findClosestPair(int[] arr1, int[] arr2, int x)
{
int n = arr1.length;
int m = arr2.length;
int l = 0, r = m - 1;
int diff = Integer.MAX_VALUE;
ArrayList<Integer> result = new ArrayList<>();
// Traverse both arrays using two pointers
while (l < n && r >= 0)
{
int sum = arr1[l] + arr2[r];
int currDiff = Math.abs(sum - x);
// Update result if closer pair is found
if (currDiff < diff)
{
diff = currDiff;
result.clear();
result.add(arr1[l]);
result.add(arr2[r]);
}
// Move pointers to bring sum closer to x
if (sum > x)
r--;
else
l++;
}
return result;
}
public static void main(String[] args)
{
int[] arr1 = {1, 4, 5, 7};
int[] arr2 = {10, 20, 30, 40};
int x = 38;
ArrayList<Integer> closest = findClosestPair(arr1, arr2, x);
System.out.println(closest);
}
}
import math
def findClosestPair(arr1, arr2, x):
n = len(arr1)
m = len(arr2)
l, r = 0, m - 1
diff = float('inf')
result = [0, 0]
# Traverse both aays using two pointers
while l < n and r >= 0:
sum_val = arr1[l] + arr2[r]
currDiff = abs(sum_val - x)
# Update result if closer pair is found
if currDiff < diff:
diff = currDiff
result[0] = arr1[l]
result[1] = arr2[r]
# Move pointers to bring sum closer to x
if sum_val > x:
r -= 1
else:
l += 1
return result
if __name__ == "__main__":
arr1 = [1, 4, 5, 7]
arr2 = [10, 20, 30, 40]
x = 38
closest = findClosestPair(arr1, arr2, x)
print(closest)
using System;
using System.Collections.Generic;
class GfG
{
static List<int> findClosestPair(int[] arr1, int[] arr2, int x)
{
int n = arr1.Length;
int m = arr2.Length;
int l = 0, r = m - 1;
int diff = int.MaxValue;
List<int> result = new List<int>();
// Traverse both aays using two pointers
while (l < n && r >= 0)
{
int sum = arr1[l] + arr2[r];
int currDiff = Math.Abs(sum - x);
// Update result if closer pair is found
if (currDiff < diff)
{
diff = currDiff;
result.Clear();
result.Add(arr1[l]);
result.Add(arr2[r]);
}
// Move pointers to bring sum closer to x
if (sum > x)
r--;
else
l++;
}
return result;
}
static void Main()
{
int[] arr1 = {1, 4, 5, 7};
int[] arr2 = {10, 20, 30, 40};
int x = 38;
List<int> closest = findClosestPair(arr1, arr2, x);
Console.WriteLine("[" + closest[0] + ", " + closest[1] + "]");
}
}
function findClosestPair(arr1, arr2, x)
{
let n = arr1.length;
let m = arr2.length;
let l = 0, r = m - 1;
let diff = Number.MAX_SAFE_INTEGER;
let result = [0, 0];
// Traverse both aays using two pointers
while (l < n && r >= 0)
{
let sum = arr1[l] + arr2[r];
let currDiff = Math.abs(sum - x);
// Update result if closer pair is found
if (currDiff < diff)
{
diff = currDiff;
result[0] = arr1[l];
result[1] = arr2[r];
}
// Move pointers to bring sum closer to x
if (sum > x)
r--;
else
l++;
}
return result;
}
// Driver Code
let arr1 = [1, 4, 5, 7];
let arr2 = [10, 20, 30, 40];
let x = 38;
let closest = findClosestPair(arr1, arr2, x);
console.log(`[${closest[0]}, ${closest[1]}]`);
Output
[7, 30]