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:
        print("Pair Not Found")

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
	{
		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.

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.

New Comment