Find the closest pair from two sorted arrays
The problem of finding the closest pair from two sorted arrays involves identifying two elements, one from each array, that have the smallest absolute difference compared to a given target element. This problem arises in various scenarios such as optimization algorithms, data analysis, and real-time systems. In this article, we'll delve into the details of solving this problem, provide a step-by-step approach, explain the algorithm, and analyze its time complexity.
Problem Statement
Given two sorted arrays and a target element, the task is to find and display a pair of elements (one from each array) that have the smallest absolute difference compared to the target element.
Example
Consider two sorted arrays: Array 1: [1, 9, 13, 14] Array 2: [-5, 0, 1, 8, 9, 13, 14, 21] Target Element: 7
The closest pair with the smallest absolute difference to the target element 7 is (13, -5), as (13 + -5) equals 8.
Idea to Solve the Problem
To solve this problem, we can use a two-pointer approach where we initialize one pointer at the beginning of the first array and the other pointer at the end of the second array. We calculate the absolute difference between the sum of the elements pointed by the two pointers and the target element. By comparing this difference and updating pointers based on the comparison, we can find the closest pair.
Pseudocode
closest_pair(arr1, arr2, s1, s2, element):
i = 0
j = s2 - 1
result = INT_MAX
first = -1
second = -1
while i < s1 and j >= 0:
difference = abs(arr1[i] + arr2[j] - element)
if difference < result:
first = i
second = j
result = difference
if arr1[i] + arr2[j] > element:
j -= 1
else:
i += 1
if first != -1 and second != -1:
print("Closest pair:", arr1[first], arr2[second])
else:
print("Pair Not Found")Algorithm Explanation
- Initialize pointers
iandjat the beginning of the first array and the end of the second array, respectively. - Initialize variables
result,first, andsecondto store the minimum absolute difference, indices of the closest pair, and the absolute difference, respectively. - Enter a loop that continues until
iis within the bounds of the first array andjis within the bounds of the second array. - Calculate the absolute difference between the sum of the elements at
iandjand the target element. - Compare the calculated difference with the current result. If it's smaller, update
first,second, andresult. - If the sum of the elements at
iandjis greater than the target element, decrementj. Otherwise, incrementi. - After the loop, if
firstandsecondare not -1, print the closest pair. Otherwise, print "Pair Not Found."
Code Solution
// C Program
// Find the closest pair from two sorted arrays
#include <stdio.h>
#include <limits.h>
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
//Find closest pair of given element in sorted array
void closest_pair(int arr1[], int arr2[], int s1, int s2, int element)
{
//Display array elements
printf("\n Array 1 :");
display(arr1, s1);
printf(" Array 2 :");
display(arr2, s2);
//Loop controlling variables
int i = 0;
int j = s2 - 1;
//Useful resultant variable
int result = INT_MAX;
int first = -1;
int second = -1;
int difference = 0;
printf(" Closest pair of element [%d] is : ", element);
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i++;
}
}
if (first != -1 && second != -1)
{
//When result are exist
printf("[(%d) + (%d)]\n", arr1[first], arr2[second]);
}
else
{
printf(" Not Found\n");
}
}
int main()
{
//Define array of integer elements
int arr1[] = {
1 , 9 , 13 , 14
};
int arr2[] = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
//Get the size of array
int s1 = sizeof(arr1) / sizeof(arr1[0]);
int s2 = sizeof(arr2) / sizeof(arr2[0]);
int element = 7;
closest_pair(arr1, arr2, s1, s2, element);
int arr3[] = {
1 , 6 , 13 , 14
};
int arr4[] = {
2 , 5 , 11 , 13 , 20
};
//Get the size of array
s1 = sizeof(arr3) / sizeof(arr3[0]);
s2 = sizeof(arr4) / sizeof(arr4[0]);
element = 10;
closest_pair(arr3, arr4, s1, s2, element);
return 0;
}Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13 20
Closest pair of element [10] is : [(6) + (5)]// Java Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Find closest pair of given element in sorted array
public void closest_pair(int[] arr1, int[] arr2, int s1, int s2, int element)
{
System.out.print("\n Array 1 :");
display(arr1, s1);
System.out.print(" Array 2 :");
display(arr2, s2);
//Loop controlling variables
int i = 0;
int j = s2 - 1;
//Useful resultant variable
int result = Integer.MAX_VALUE;
int first = -1;
int second = -1;
int difference = 0;
System.out.print(" Closest pair of element [" + element + "] is : ");
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i++;
}
}
if (first != -1 && second != -1)
{
System.out.print("[(" + arr1[first] + ") + (" + arr2[second] + ")]\n");
}
else
{
System.out.print(" Not Found\n");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array of integer elements
int[] arr1 = {
1,
9,
13,
14
};
int[] arr2 = {
-5,
0,
1,
8,
9,
13,
14,
21
};
//Get the size of array
int s1 = arr1.length;
int s2 = arr2.length;
int element = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
int[] arr3 = {
1,
6,
13,
14
};
int[] arr4 = {
2,
5,
11,
13,
20
};
//Get the size of array
s1 = arr3.length;
s2 = arr3.length;
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
}
}Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]//Include header file
#include <iostream>
#include<limits.h>
using namespace std;
// C++ Program
// Find the closest pair from two sorted arrays
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Find closest pair of given element in sorted array
void closest_pair(int arr1[], int arr2[], int s1, int s2, int element)
{
cout << "\n Array 1 :";
this->display(arr1, s1);
cout << " Array 2 :";
this->display(arr2, s2);
//Loop controlling variables
int i = 0;
int j = s2 - 1;
//Useful resultant variable
int result = INT_MAX;
int first = -1;
int second = -1;
int difference = 0;
cout << " Closest pair of element [" << element << "] is : ";
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i++;
}
}
if (first != -1 && second != -1)
{
cout << "[(" << arr1[first] << ") + (" << arr2[second] << ")]\n";
}
else
{
cout << " Not Found\n";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
1 , 9 , 13 , 14
};
int arr2[] = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
//Get the size of array
int s1 = sizeof(arr1) / sizeof(arr1[0]);
int s2 = sizeof(arr2) / sizeof(arr2[0]);
int element = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
int arr3[] = {
1 , 6 , 13 , 14
};
int arr4[] = {
2 , 5 , 11 , 13 , 20
};
//Get the size of array
s1 = sizeof(arr3) / sizeof(arr3[0]);
s2 = sizeof(arr3) / sizeof(arr3[0]);
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
return 0;
}Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]//Include namespace system
using System;
// C# Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Find closest pair of given element in sorted array
public void closest_pair(int[] arr1, int[] arr2, int s1, int s2, int element)
{
Console.Write("\n Array 1 :");
display(arr1, s1);
Console.Write(" Array 2 :");
display(arr2, s2);
//Loop controlling variables
int i = 0;
int j = s2 - 1;
//Useful resultant variable
int result = int.MaxValue;
int first = -1;
int second = -1;
int difference = 0;
Console.Write(" Closest pair of element [" + element + "] is : ");
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i++;
}
}
if (first != -1 && second != -1)
{
Console.Write("[(" + arr1[first] + ") + (" + arr2[second] + ")]\n");
}
else
{
Console.Write(" Not Found\n");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
1 , 9 , 13 , 14
};
int[] arr2 = {
-5 , 0 , 1 , 8 , 9 , 13 , 14 , 21
};
//Get the size of array
int s1 = arr1.Length;
int s2 = arr2.Length;
int element = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
int[] arr3 = {
1 , 6 , 13 , 14
};
int[] arr4 = {
2 , 5 , 11 , 13 , 20
};
//Get the size of array
s1 = arr3.Length;
s2 = arr3.Length;
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
}
}Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]<?php
// Php Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
public function display( $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
//Find closest pair of given element in sorted array
public function closest_pair( $arr1, $arr2, $s1, $s2, $element)
{
echo "\n Array 1 :";
$this->display($arr1, $s1);
echo " Array 2 :";
$this->display($arr2, $s2);
//Loop controlling variables
$i = 0;
$j = $s2 - 1;
//Useful resultant variable
$result = PHP_INT_MAX;
$first = -1;
$second = -1;
$difference = 0;
echo " Closest pair of element [". $element ."] is : ";
while ($i < $s1 && $j >= 0)
{
//Calculate difference
$difference = (($arr1[$i] + $arr2[$j]) - $element);
if ($difference < 0)
{
//When difference is negative
$difference = -$difference;
}
if ($difference < $result)
{
//When gets a new smallest closest pair
//Get location
$first = $i;
$second = $j;
//update resultant difference
$result = $difference;
}
else if ($arr1[$i] + $arr2[$j] > $element)
{
//When pair sum is more than given element
//Then reduce the index of second array
$j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
$i++;
}
}
if ($first != -1 && $second != -1)
{
echo "[(". $arr1[$first] .") + (". $arr2[$second] .")]\n";
}
else
{
echo " Not Found\n";
}
}
}
function main()
{
$obj = new MyArray();
//Define array of integer elements
$arr1 = array(1, 9, 13, 14);
$arr2 = array(-5, 0, 1, 8, 9, 13, 14, 21);
//Get the size of array
$s1 = count($arr1);
$s2 = count($arr2);
$element = 7;
$obj->closest_pair($arr1, $arr2, $s1, $s2, $element);
$arr3 = array(1, 6, 13, 14);
$arr4 = array(2, 5, 11, 13, 20);
//Get the size of array
$s1 = count($arr3);
$s2 = count($arr3);
$element = 10;
$obj->closest_pair($arr3, $arr4, $s1, $s2, $element);
}
main();Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]// Node Js Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Find closest pair of given element in sorted array
closest_pair(arr1, arr2, s1, s2, element)
{
process.stdout.write("\n Array 1 :");
this.display(arr1, s1);
process.stdout.write(" Array 2 :");
this.display(arr2, s2);
//Loop controlling variables
var i = 0;
var j = s2 - 1;
//Useful resultant variable
var result = Number.MAX_VALUE;
var first = -1;
var second = -1;
var difference = 0;
process.stdout.write(" Closest pair of element [" + element + "] is : ");
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j--;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i++;
}
}
if (first != -1 && second != -1)
{
process.stdout.write("[(" + arr1[first] + ") + (" + arr2[second] + ")]\n");
}
else
{
process.stdout.write(" Not Found\n");
}
}
}
function main()
{
var obj = new MyArray();
//Define array of integer elements
var arr1 = [1, 9, 13, 14];
var arr2 = [-5, 0, 1, 8, 9, 13, 14, 21];
//Get the size of array
var s1 = arr1.length;
var s2 = arr2.length;
var element = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
var arr3 = [1, 6, 13, 14];
var arr4 = [2, 5, 11, 13, 20];
//Get the size of array
s1 = arr3.length;
s2 = arr3.length;
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
}
main();Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]import sys
# Python 3 Program
# Find the closest pair from two sorted arrays
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# Find closest pair of given element in sorted array
def closest_pair(self, arr1, arr2, s1, s2, element) :
print("\n Array 1 :", end = "")
self.display(arr1, s1)
print(" Array 2 :", end = "")
self.display(arr2, s2)
# Loop controlling variables
i = 0
j = s2 - 1
# Useful resultant variable
result = sys.maxsize
first = -1
second = -1
difference = 0
print(" Closest pair of element [", element ,"] is : ", end = "")
while (i < s1 and j >= 0) :
# Calculate difference
difference = ((arr1[i] + arr2[j]) - element)
if (difference < 0) :
# When difference is negative
difference = -difference
if (difference < result) :
# When gets a new smallest closest pair
# Get location
first = i
second = j
# update resultant difference
result = difference
elif(arr1[i] + arr2[j] > element) :
# When pair sum is more than given element
# Then reduce the index of second array
j -= 1
else :
# When resultant pair is less than given element
# Then increase the first array index
i += 1
if (first != -1 and second != -1) :
print("[(", arr1[first] ,") + (", arr2[second] ,")]\n", end = "")
else :
print(" Not Found\n", end = "")
def main() :
obj = MyArray()
# Define array of integer elements
arr1 = [1, 9, 13, 14]
arr2 = [-5, 0, 1, 8, 9, 13, 14, 21]
# Get the size of array
s1 = len(arr1)
s2 = len(arr2)
element = 7
obj.closest_pair(arr1, arr2, s1, s2, element)
arr3 = [1, 6, 13, 14]
arr4 = [2, 5, 11, 13, 20]
# Get the size of array
s1 = len(arr3)
s2 = len(arr3)
element = 10
obj.closest_pair(arr3, arr4, s1, s2, element)
if __name__ == "__main__": main()Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [ 7 ] is : [( 13 ) + ( -5 )]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [ 10 ] is : [( 6 ) + ( 5 )]# Ruby Program
# Find the closest pair from two sorted arrays
class MyArray
# Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Find closest pair of given element in sorted array
def closest_pair(arr1, arr2, s1, s2, element)
print("\n Array 1 :")
self.display(arr1, s1)
print(" Array 2 :")
self.display(arr2, s2)
# Loop controlling variables
i = 0
j = s2 - 1
# Useful resultant variable
result = (2 ** (0. size * 8 - 2))
first = -1
second = -1
difference = 0
print(" Closest pair of element [", element ,"] is : ")
while (i < s1 && j >= 0)
# Calculate difference
difference = ((arr1[i] + arr2[j]) - element)
if (difference < 0)
# When difference is negative
difference = -difference
end
if (difference < result)
# When gets a new smallest closest pair
# Get location
first = i
second = j
# update resultant difference
result = difference
elsif(arr1[i] + arr2[j] > element)
# When pair sum is more than given element
# Then reduce the index of second array
j -= 1
else
# When resultant pair is less than given element
# Then increase the first array index
i += 1
end
end
if (first != -1 && second != -1)
print("[(", arr1[first] ,") + (", arr2[second] ,")]\n")
else
print(" Not Found\n")
end
end
end
def main()
obj = MyArray.new()
# Define array of integer elements
arr1 = [1, 9, 13, 14]
arr2 = [-5, 0, 1, 8, 9, 13, 14, 21]
# Get the size of array
s1 = arr1.length
s2 = arr2.length
element = 7
obj.closest_pair(arr1, arr2, s1, s2, element)
arr3 = [1, 6, 13, 14]
arr4 = [2, 5, 11, 13, 20]
# Get the size of array
s1 = arr3.length
s2 = arr3.length
element = 10
obj.closest_pair(arr3, arr4, s1, s2, element)
end
main()Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]
// Scala Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Find closest pair of given element in sorted array
def closest_pair(arr1: Array[Int], arr2: Array[Int], s1: Int, s2: Int, element: Int): Unit = {
print("\n Array 1 :");
display(arr1, s1);
print(" Array 2 :");
display(arr2, s2);
//Loop controlling variables
var i: Int = 0;
var j: Int = s2 - 1;
//Useful resultant variable
var result: Int = Int.MaxValue;
var first: Int = -1;
var second: Int = -1;
var difference: Int = 0;
print(" Closest pair of element [" + element + "] is : ");
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1(i) + arr2(j)) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1(i) + arr2(j) > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j -= 1;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i += 1;
}
}
if (first != -1 && second != -1)
{
print("[(" + arr1(first) + ") + (" + arr2(second) + ")]\n");
}
else
{
print(" Not Found\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array of integer elements
var arr1: Array[Int] = Array(1, 9, 13, 14);
var arr2: Array[Int] = Array(-5, 0, 1, 8, 9, 13, 14, 21);
//Get the size of array
var s1: Int = arr1.length;
var s2: Int = arr2.length;
var element: Int = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
var arr3: Array[Int] = Array(1, 6, 13, 14);
var arr4: Array[Int] = Array(2, 5, 11, 13, 20);
//Get the size of array
s1 = arr3.length;
s2 = arr3.length;
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
}
}Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [7] is : [(13) + (-5)]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [10] is : [(6) + (5)]// Swift Program
// Find the closest pair from two sorted arrays
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find closest pair of given element in sorted array
func closest_pair(_ arr1: [Int], _ arr2: [Int], _ s1: Int, _ s2: Int, _ element: Int)
{
print("\n Array 1 :", terminator: "");
self.display(arr1, s1);
print(" Array 2 :", terminator: "");
self.display(arr2, s2);
//Loop controlling variables
var i: Int = 0;
var j: Int = s2 - 1;
//Useful resultant variable
var result: Int = Int.max;
var first: Int = -1;
var second: Int = -1;
var difference: Int = 0;
print(" Closest pair of element [", element ,"] is : ", terminator: "");
while (i < s1 && j >= 0)
{
//Calculate difference
difference = ((arr1[i] + arr2[j]) - element);
if (difference < 0)
{
//When difference is negative
difference = -difference;
}
if (difference < result)
{
//When gets a new smallest closest pair
//Get location
first = i;
second = j;
//update resultant difference
result = difference;
}
else if (arr1[i] + arr2[j] > element)
{
//When pair sum is more than given element
//Then reduce the index of second array
j -= 1;
}
else
{
//When resultant pair is less than given element
//Then increase the first array index
i += 1;
}
}
if (first != -1 && second != -1)
{
print("[(", arr1[first] ,") + (", arr2[second] ,")]\n", terminator: "");
}
else
{
print(" Not Found\n", terminator: "");
}
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array of integer elements
let arr1: [Int] = [1, 9, 13, 14];
let arr2: [Int] = [-5, 0, 1, 8, 9, 13, 14, 21];
//Get the size of array
var s1: Int = arr1.count;
var s2: Int = arr2.count;
var element: Int = 7;
obj.closest_pair(arr1, arr2, s1, s2, element);
let arr3: [Int] = [1, 6, 13, 14];
let arr4: [Int] = [2, 5, 11, 13, 20];
//Get the size of array
s1 = arr3.count;
s2 = arr3.count;
element = 10;
obj.closest_pair(arr3, arr4, s1, s2, element);
}
main();Output
Array 1 : 1 9 13 14
Array 2 : -5 0 1 8 9 13 14 21
Closest pair of element [ 7 ] is : [( 13 ) + ( -5 )]
Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element [ 10 ] is : [( 6 ) + ( 5 )]Time Complexity Analysis
The algorithm traverses both arrays once using the two-pointer approach. Therefore, the time complexity is O(s1 +
s2), where s1 and s2 are the sizes of the two arrays. In the worst case, this approach
ensures efficient performance even for larger arrays.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment