CareerCup

int i(0), j(0);
while (i < a.size() && j < b.size()) {
   if (a[i] <= b[j]) {  ans = min(ans, b[j]-a[i]); i++; } 
   else { ans = min(ans, a[i]-b[j]); j++; }
}
return ans;

for(int i=0;i<n1;i++)
{
for(j=0;<j<n2;j++)
{
s[k]=Abs(a[i]-a[j])
k=k+1;
}
}
small=s[0];
for(int i=1;i<n1*n2;i++)
{
if(a[i]<small)
{
small=a[i];
}
}
printf("smallest diff is %d",small);

//We do what's basically the merge step of mergesort.
//Let the two arrays be
int a[m], b[n];

int i=0, j=0, k=0;
int diff = MAXINT,  cdiff;
while (i < m && j < n)
{
	while (a[i] < b[j]) 
	{
		cdiff = b[j] - a[i];
		i++;
		if (cdiff < diff) diff = cdiff;
		if (i == m) return diff;
	}
	while (b[j] < a[i])
	{
		cdiff = b[j] - a[i];
		j++;
		if (cdiff < diff) diff = cdiff;
		if (j == n) return diff;
	}
}
return diff;

let l1 and l2 be lengths of smaller and larger arrays resp.
this is an O(l1*log(l2)) soln I could think of :-
1)fix the min to be INT_MAX
2)Iterate from 0 to l1-1 :-
2.1)find the element in arr2 which is just less than arr1[i] // i : 1 to l1-1
2.2)find the closest elem in arr2 for the arr1[i] element and see if abs-diff is smaller than min .

public class MinimumDiffBetweenArrays {
public static void main(String[] args) {
int i=0,j=0, min;
int[] a = {1,2,3,9};
int[] b = {7,10,16,19};
int ans = Math.abs(a[i]-b[j]);
while(i<a.length && j<b.length) {
if(a[i] < b[j]) {
min = b[j] - a[i];
i++;
} else {
min = a[i] - b[j];
j++;
}
ans = ans>min?min:ans;
}
System.out.println(ans);
}
}

#include<iostream>
#include<cmath>

using namespace std;

int findSmallestPossibleDifference(int a1[], int a2[], int n, int m)
{
	int minDiff = 9999999;
	
	for (int i = 0; i < n; i++)
	{
		int l = 0;
		int h = m - 1;
		
		// Searching each element in smaller array in the larger array
		while (l < h)
		{
			int mid = l + (h - l)/2;
			
			if(a2[mid] == a1[i])    return 0;
			else if(a1[i] < a2[mid])
			{
				h = mid - 1;
			}
			else l = mid + 1;
		}
		
		int lhsDiff = 999999, rhsDiff = 999999;
		if(l > 0) lhsDiff = abs(a2[l] - a1[i]);
		if(l < m) rhsDiff = abs(a2[l] - a1[i]);
		
		minDiff = min(minDiff, min(lhsDiff, rhsDiff));
	}

	return minDiff;
}


int main()
{
	int n = 5;
	int m = 10;
	int a1[5] = {2, 4, 7, 9, 19};
	int a2[10] = {-3, 12, 14, 15, 23, 26, 30, 32, 35, 40};
	
	cout <<	endl << findSmallestPossibleDifference(a1, a2, n, m);

	return 0;
}

O( n log m ) where n is the size of the smaller array and m is the size of the larger array.

public class MinDifference {
    
    public static int findMinDifference(int[] A, int[] B) {
        int min = Integer.MAX_VALUE;
        
        // Go through A and find adjacent differences
        for( int i = 0; i < A.length-1; i++ ) {
            min = MIN( min, Math.abs(A[i] - A[i+1]) );
        }
        
        // Go through B and find adjacent differences
        for( int i = 0; i < B.length-1; i++ ) {
            min = MIN( min, Math.abs(B[i] - B[i+1]) );
        }
        
        // Find minimum differences between both arrays
        if( A.length <= B.length ) {
            for( int i = 0; i < A.length; i++ ) {
                int index = findIndexFor(B, A[i]);    // Find where A[i] would be in B
                min = MIN( min, Math.abs(A[i] - B[index]) );
            }
        } else {
            for( int i = 0; i < B.length; i++ ) {
                int index = findIndexFor(A, B[i]);    // Find where B[i] would be in A
                min = MIN( min, Math.abs(B[i] - A[index]) );
            }
        }
        return min;
    }
    
    // Binary search
    private static int findIndexFor( int[] arr, int elem ) {
        int l = 0, m = arr.length/2, r = arr.length - 1;
        
        while( l < r ) {
        	m = (l+r)/2;
            if( elem < arr[m] ) {
                r = m - 1;
            } else if ( elem > arr[m] ) {
                l = m + 1;
            } else {    // elem == arr[m]
                return m;
            }
        }
        return r;
    }
    
    private static int MIN( int a, int b ) {
        return (a < b)? a : b;
    }
    
    public static void main(String[] args) {
    	int[] A = {1, 4, 7, 10, 19};
    	int[] B = {-3, 12, 15, 23, 26, 30, 33, 36, 40};
    	System.out.println("Minimum Diff: " + findMinDifference(A,B));
    }
}

O(n + m)

public static int findMinDifferenceBetter(int[] A, int[] B) {
    	int min = Integer.MAX_VALUE;
    	int[] merged = new int[A.length + B.length];
        
        // Merge part of merge sort
        for( int i = 0, j = 0, k = 0; k < A.length + B.length; k++ ) {
        	if( i == A.length ) { merged[k] = B[j++]; continue;}
        	if( j == B.length ) { merged[k] = A[i++]; continue;}
        	merged[k] = (A[i] < B[j])? A[i++] : B[j++];
        }
        
        for( int i = 0; i < merged.length-1; i++ ) {
        	min = MIN( min, Math.abs(merged[i] - merged[i+1]) );
        }
        return min;
    }

#include <stdio.h>

int main() {
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
int i, j;
int diff, tmp1, tmp2;
i = j = 0;
diff = abs(a[i] - b[j]);
while(i < 5 && j < 5) {
tmp1 = abs(a[i] - b[j+1]);
tmp2 = abs(a[i+1] - b[j]);
printf("i= %d\t j= %d\t diff= %d\t tmp1= %d\t tmp2= %d\n", i, j, diff, tmp1, tmp2);
if(tmp1 < tmp2 && tmp1 < diff) {
diff = tmp1;
j++;
continue;
}
if(tmp2 < tmp1 && tmp2 < diff) {
diff = tmp2;
i++;
continue;
}
if(tmp1 == tmp2 && tmp1 < diff) {
diff = tmp1;
}
i++; j++;
}

printf("%d\n", diff);
return 0;
}

#include<iostream>
#include<string.h>
using namespace std; 

int main( )
{
//  int a[] = { 0, 1, 2, 3, 4 }, b[] = { 5, 6, 7, 8, 9 };
    int a[] = { -4,-3,-2,-1 }, b[] = { -9,-8,-7,-3,-2};
    int aLen = sizeof(a)/sizeof(a[0]), bLen = sizeof(b)/sizeof(b[0]);
    int i=0, j=0;
    int retVal = max(a[aLen-1] , b[bLen-1]) + 1;
   // give retVal a value which is strictly greater than any other array value
   // remove "+1" & to get a wrong answer

    while( i < aLen && j < bLen )
    {
        if( a[i] <= b[j] )        {  retVal = min(retVal, b[j]-a[i]);   i++;   }
        else                       {  retVal = min(retVal, a[i]-b[j]);   j++;   }
    }
    cout << retVal;
    return 0;
}

O(nlogm):

for each element in A, use Binary Search method to find the element with the closest value in array B.

#include <iostream>
#include <queue>

using namespace std;

int binSearch(int *arr, int size, int num) {

  int low = 0;
  int high = size - 1;
  int result = -1;
  
  while (low <= high) {
      int mid = (low + high) / 2;
      
      if (num < arr[mid]) {
          high = mid - 1;
      } else if (num > arr[mid]) {
          low = mid + 1;
          result = mid;
      } else {
          // FOUND;
          return mid;
      }
  }
  if (result == -1)
  return size - 1;
}

int abs(int a) {
    if (a < 0)
    return a * -1;
}

int main () {
    
  int arr1[] = { 0, 1, 2, 3, 4 };
  int arr1_size = sizeof(arr1) / sizeof(*arr1);
  
  int arr2[] = { 5, 6, 7, 8, 9 };
  int arr2_size = sizeof(arr2) / sizeof(*arr2);
  
  std::priority_queue<int, std::vector<int>, std::greater<int> > myQ;
  
  for (int i = 0; i < arr1_size; i++) {
      int index = binSearch(arr2, arr2_size, arr1[i]);
      
      cout << "Found: " << arr1[index] << ", for "<< arr2[i]<<endl;
      if (index != -1)
        myQ.push(abs(arr1[index] - arr2[i]));
  }
  
  int q_size = myQ.size();
  for (int i = 0; i < q_size; i++) {
    cout << myQ.top() << endl;
    myQ.pop();
  }
  
  return 0;    
}

private static int find_min_diff(int[] a, int[] b) {
		int i = 0;
		int j = 0;
		int diff = 0;
		int min_diff = Integer.MAX_VALUE;
		while (i < a.length && j < b.length) {

			diff = Math.abs(a[i] - b[j]);
			if (diff == 1)
				return 1;
			if (diff < b[j])
				i++;
			else {
				i++;
				j++;
			}

			if (diff < min_diff)
				min_diff = diff;

		}

		return min_diff;
	}

//because the input is sorted. ( example input be 1 2 3 as array1 and -6 -5 -) I do not think we need to scan whole array

findMinDiff( int[] sorted1, int[] sorted2){
int start1 = sorted1[0];
int end1 = sorted1[sorted1.length -1 ];
int start2 = sorted2[0];
int end2 = sorted2[sorted2.length -1 ];
int diff1 = Math.abs(start1 - end2);
int diff2 = Math.abs(start2 -end1);
if( diff1 < diff 2) return diff1
return diff2;
}




}

I think this also works. iteratively checking each value
Time Complexity: O(n)
Space Complexity: no additional buffers needed.

import java.lang.math.*;

int findAbsMin(ArrayList<Integer> a, ArrayList<Integer> b){
    if(a.size() == 0 || b.size() == 0) return 0;
    if(a.size() == 1 && b.size() == 1) return Math.abs(a[a.size()] - b[b.si[bze()]);
    
    int min = Math.abs(a[a.size()] - b[b.size()]); //set to randome value
    int x = 0, y =0;
    while(true){
        if(Math.abs(a[x] - b[y]) < min)
        {
            min = Math.abs(a[x] - b[y]); 
            if(a[x] > b[y] && y <= b.size())
                y++;
            else if(a[x] < b[y] && x <= a.size())
                x++;
            else
                break;
            
        }
        else{
            if(a[x] > b[y] && y <= b.size())
                y++;
            else if(a[x] < b[y] && x <= a.size())
                x++;
            else
                break;//done iterating
        }
    }
    return min;
}

Find out three min,
1) minimum in array 1
2) Minimum in Array 2
3) Minimum among arrays
then return minimum of these 3 minimum.

public static int getMinDiff(int a[] ) { 
		int n = a.length;
		int min = Integer.MAX_VALUE;
		for(int i = 1 ; i < n; i++) {
			min = Math.min(min, a[i] - a[i-1]);
		}
		return min;
	}
	public static int getMin(int a[], int b[]) {
		int min1 = getMinDiff(a);
		int min2 =  getMinDiff(b);
		int n1 = a.length;
		int n2 = b.length;
		int i = 0;
		int j = 0;
		int min3 = Integer.MAX_VALUE;
		while(i < n1 && j < n2) {
			if(a[i] <= b[j]) {
				min3 = Math.min(min3, b[j] - a[i]);
				i++;
			} else {
				min3 = Math.min(min3, a[i] - b[j]);
				j++;
			}
		}
		
		return (Math.min(min1, Math.min(min2, min3)));
	}