Thursday, May 28, 2015

L Question: Min Difference Between Two Arrays

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));
    }
}

No comments:

Post a Comment