CareerCup

This is exactly same to the case of "merge"-ing in merge-sort.
Two sorted arrays can merged in linear time. And while merging, absolute difference between any pair of consecutive elements in the final sorted array is stored (along with the pair), such that it is lesser than previous one.

Hence the final value yields the required result.

Algo:
1. Take two variable ptr1 and ptr2. Initialized both of them to zero
2. Take 3rd variable diff initialized with INT_MAX
3. While (ptr1 < arr1.length || ptr2 < arr1.length){
If(diff > abs(arr[ptr1] – arr[ptr2])){
Diff = abs(arr[ptr1] – arr[ptr2])
}
If(arr[ptr1] > arr[ptr2])
Ptr2++;
Else
Ptr1++;

}

Please advise guys ??

The answer has already been posted, but for anyone that wants some working code, this should do the trick:

private static int[] closestNumbers(int[] a1, int[] a2) {
	int i = 0, j = 0;
	int x = 0, y = Integer.MAX_VALUE;
	
	while (true) {
		if (Math.abs(a1[i] - a2[j]) < Math.abs(x - y)) {
			x = a1[i];
			y = a2[j];
		}
		
		if (i < a1.length - 1 && a1[i] < a2[j]) i++;
		else if (j < a2.length - 1) j++;
		else break;
	}
	
	return new int[] { x, y };
}

Someone please correct me if you see anything wrong.

public static void getMinAbsDiff(int[] A, int[] B)
	{
		int lenA = A.length;
		int lenB = B.length;

		int diff;
		int i = 0; //index to traverse Array A
		int j = 0; // index to traverse Array B
		int minDiff = Integer.MAX_VALUE; // default min Diff 

		while(i < lenA && j < lenB)
		{
			// if A[i] <= B[j] finding the diff and incrementing the lower value index
			if (A[i] <= B[j])
			{
				diff = Math.abs(A[i] - B[j]);
				i++;
			}
			else
			{
				diff = Math.abs(A[i] - B[j]); // else incrementing the jth index
				j++;
			}
			
			if (diff < minDiff) // updating the minimum diff value.
				minDiff = diff;
		}
		System.out.println("Min Diff :" + minDiff);

}

Hey I happen to saw this algorithm is an open course: first sort array 1, then for each element in array 2, use binary search to find the element in array 1 that forms the smallest gap with it, store it, then look for the minimum among all such differences. The algorithm takes O(n lg n) time.

public class Test {

public static void main(String[] args){

int arr1[]={13,19,21,37,89};
int arr2[]={23,30,45,67,99};

int min = Math.abs(arr1[0]-arr2[0]);

for(int i=0;i<5;i++){
for(int j=0;j<5;j++){

if(Math.abs(arr1[i]-arr2[j]) < min){

min = Math.abs(arr1[i]-arr2[j]);
}
}
}
System.out.println(min);
}
}

I feel this should be done in o(n)

static int GetMinAbsoluteDiff(int[] a, int[] b)
        {
            int minDif = int.MaxValue;
            int i = 0;
            minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
            minDif = Math.Min(minDif, Math.Abs(a[i] - b[i + 1]));
            for (i = 1; i < a.Length-1; i++)
            {
                minDif = Math.Min(minDif, Math.Abs(a[i] - b[i-1]));
                minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
                minDif = Math.Min(minDif, Math.Abs(a[i] - b[i+1]));
            }
            minDif = Math.Min(minDif, Math.Abs(a[i] - b[i - 1]));
            minDif = Math.Min(minDif, Math.Abs(a[i] - b[i]));
            return minDif;
        }

Correct me if there are any complexities involved in it.

This problem is similar to merging except we need to tweak it a bit

So, the main criteria we need is that the previous element inserted while merging should be from the other array and the present element to be inserted should be from this array, hence we can keep a boolean value to indicate from which array was the last element was inserted.
now while inserting an element, check from where was the last element was inserted, if from the same array do nothing, if from the other array, check the difference and update the values if the difference turns out to be lesser than the previous value

the only other change is to make the while loop as
while(i < size1 && j < size2) instead of while(i < size1 || j < size2)

Do it in O(N) time, simulating the merge stage of the merge sort algo and keeping track of the absolute difference between any current elements of the array. Below is the s/c and the test driver:

#include <stdio.h>

int absdiff(int a, int b)
{
    if (a == b)
        return 0;        
    if (a > b)
        return (a - b);        
    return (b - a);
}

int min_diff_els(int a[], int b[], int size, int& idx1, int& idx2)
{
    int i = 0, j = 0;
    idx1 = 0;
    idx2 = 0;
    int mindiff;

    mindiff = absdiff(a[0], b[0]);
    
    // special case when there is no better solution,
    // since absdiff(a, b) can't be < 0
    if (0 == mindiff)
        return 0;
    
    ++i; ++j;
    while (i < size && j < size){
        int cv = absdiff(a[i], b[j]);
        if (cv < mindiff) {
            idx1 = i;
            idx2 = j;
            mindiff = cv;
        }
        
        if (a[i] < b[j])
            ++i;
        else
            ++j;
    }
    
    return mindiff;
}

int main()
{
    // 
    int a[] = {5, 9, 12, 15, 18, 25};
    int b[] = {1, 3, 6, 10, 17, 22};
    int size = sizeof(a)/sizeof(a[0]);
    
    int idx1, idx2, val;
    val = min_diff_els(a, b, size, idx1, idx2);
    
    printf("Min Abs Diff: %-3d Idx1: %-3d Idx2: %-3d\n",
            val, idx1, idx2);
    
    return 0;
}

suppose we take two array a[ ],b[ ] of same size let n
take variable min=10,diff=0,c,d

for(i=0;i<n;i++){
for(j=0;j<n;j++){
diff=a[i]-b[j];
if(diff<min){
min=diff;
c=a[i];
d=b[j];
}
}
}

printf("Pairs are %d %d",c,d);

is this code is correct?

Merge both the arrays and compute the difference between successive elements and keep track of the min difference