Find the closest pair from two sorted arrays
Last Updated : 29 Oct, 2025
Given two arrays arr1[0…m-1] and arr2[0…n-1], 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]
[Approach] Find the closest pair from two sorted arrays using Nested Loop:
A Simple Solution is to run two loops. The outer loop considers every element of first array and inner loop checks for the pair in second array. We keep track of minimum difference between ar1[i] + ar2[j] and x.
[Expected Approach] Sorting and Binary Search:
The key idea is to sort one of the arrays (say arr2) so we can efficiently find, for each element in arr1, the element in arr2 that makes the sum closest to x. For every arr1[i], we look for the value x - arr1[i] in arr2 using binary search. Since the exact value might not exist, we compare the closest elements around the found position to determine which gives the smaller absolute difference. This way, we minimize the difference without checking every possible pair.
C++ #include <iostream> #include <vector> #include <climits> #include <cstdlib> 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; } // Function to find the closest pair sum to x using binary search 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() { // Input arrays and target sum 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); // Print the result cout << "[" << closest[0] << ", " << closest[1] << "]" << endl; return 0; } import java.util.*; class Main { // 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; } // Function to find the closest pair sum to x using binary search 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) { // Input arrays and target sum 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); // Print the result 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 # Function to find the closest pair sum to x using binary search 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 # Input arrays and target sum arr1 = [1, 4, 5, 7] arr2 = [10, 20, 30, 40] x = 38 # Find the closest pair closest = findClosestPair(arr1, arr2, x) # Print the result print(f"[{closest[0]}, {closest[1]}]") using System; using System.Collections.Generic; class Program { // 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; } // Function to find the closest pair sum to x using binary search 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() { // Input arrays and target sum 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); // Print the result 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 to find the closest pair sum to x using binary search 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; } // Input arrays and target sum 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); // Print the result console.log(`[${closest[0]}, ${closest[1]}]`); Time Complexity : O(n*logm)
Auxiliary Space : O(1)
Smallest Difference pair of values between two unsorted Arrays
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile