Posted on by Kalkicode
Code Array

# 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:

## Algorithm Explanation

1. Initialize pointers `i` and `j` at the beginning of the first array and the end of the second array, respectively.
2. Initialize variables `result`, `first`, and `second` to store the minimum absolute difference, indices of the closest pair, and the absolute difference, respectively.
3. Enter a loop that continues until `i` is within the bounds of the first array and `j` is within the bounds of the second array.
4. Calculate the absolute difference between the sum of the elements at `i` and `j` and the target element.
5. Compare the calculated difference with the current result. If it's smaller, update `first`, `second`, and `result`.
6. If the sum of the elements at `i` and `j` is greater than the target element, decrement `j`. Otherwise, increment `i`.
7. After the loop, if `first` and `second` are 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
{
}
}
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);
int s2 = sizeof(arr2) / sizeof(arr2);
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);
s2 = sizeof(arr4) / sizeof(arr4);
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   is : [(13) + (-5)]

Array 1 :  1  6  13  14
Array 2 :  2  5  11  13  20
Closest pair of element   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
{
}
}
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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
};
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);
int s2 = sizeof(arr2) / sizeof(arr2);
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);
s2 = sizeof(arr3) / sizeof(arr3);
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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
}

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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
}

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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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 :

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

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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
}
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  is : [(13) + (-5)]

Array 1 : 1 6 13 14
Array 2 : 2 5 11 13
Closest pair of element  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
{
}
}
}
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.

## Comment

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.

Categories
Relative Post