Minimum difference in two sorted arrays

Given two sorted arrays of same length, find pairs of numbers (one from each array) which has the minimum distance between those two numbers. This is the last weeks Thursday Coding Puzzle. Since both arrays are sorted, binary search is going be really useful in searching the values in arrays.
Even though this problem is not related to finding the exact matches as in binary search, it is easy to solve this problem with the same approach used in binary search. As a preparation for this puzzle, it is really useful if you can try and write binary search yourself without referring to internet for help.

This problem can be simplified into two steps and implemented incrementally. Initially, we can simplify this problem to use only one array out of the two; then use one value from the other array rather than the second array itself. Then enhance that solution to use all values in second array against the first array to complete the answer for the problem.

One Array against One Value problem

In this problem, it is required to find a value within the array such that it is the closest to the given value. There can be one of multiple values that are the closest to a given value; so that has to be supported.

Test Cases

As usual, test cases are written first before writing any production code. Followings are the four test cases.

1. shouldReturnEmptyForAnEmptyArray
     > If the array is empty, result has to be empty

2. shouldReturnSameValueIfFoundAnywhereInGivenArray
     > If the given array contains the given value, the distance is zero (0). So it has to be returned from the array other than any value.
     e.g.: For an array with 1, 4, 7, 11 against value 4, then number pair has to be (4,4)

3. shouldReturnCorrectIfOneClosestValueIsAnywhereInGivenArray
     > If the given array contains one closest value, then that is the minimum distance. So it has to be returned with the given value.
     e.g.: For an array with 1, 4, 7, 11 against value 5, then minimum distance is 1 for the number pair (4,5) which has to be returned.

4. shouldReturnCorrectIfMultipleValuesAreTheClosest
     > If the given array contains multiple values closest to the given value, then those has to be returned with the given value.
     e.g.: For an array with 1, 4, 8, 11 against value 6, then minimum distance is 2 for the number pairs (4,6) and (6,8) which has to be returned.

Above test cases are implemented in the following manner with JUnit4.

package com.digizol.puzzle;

import static org.junit.Assert.assertEquals;
import java.util.*;
import org.junit.Test;

public class MinimumDifferencesTest {

    private MinimumDifferences sut;

    public MinimumDifferencesTest() {
        sut = new MinimumDifferences();
    }

    @Test
    public void shouldReturnEmptyForAnEmptyArray() {
        assertEquals(0, sut.getMinPair(new int[] {}, 1).length);
    }

    @Test
    public void shouldReturnSameValueIfFoundAnywhereInGivenArray() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        for (int i = 0; i < sorted.length; i++) {
            int[] result = sut.getMinPair(sorted, sorted[i]);
            assertEquals(1, result.length);
            assertEquals(sorted[i], result[0]);
        }
    }
    
    @Test
    public void shouldReturnCorrectIfOneClosestValueIsAnywhereInGivenArray() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        int[] result = sut.getMinPair(sorted, sorted[0] - 1);
        assertEquals(1, result.length);
        assertEquals(sorted[0], result[0]);

        for (int i = 0; i < sorted.length; i++) {
            result = sut.getMinPair(sorted, sorted[i] + 1);
            assertEquals(1, result.length);
            assertEquals(sorted[i], result[0]);
        }
    }

    @Test
    public void shouldReturnCorrectIfMultipleValuesAreTheClosest() {
        int[] sorted = { 1, 4, 7, 11, 15, 19, 26, 30, 33, 40 };
        int[] result = sut.getMinPair(sorted, 28);
        assertEquals(2, result.length);
        List<Integer> expected = new ArrayList<Integer>();
        expected.add(26);
        expected.add(30);

        for (int i = 0; i < result.length; i++) {
            expected.remove(Integer.valueOf(result[i]));
        }
        assertEquals(0, expected.size());
    }
}

Production Code

By simply tweaking the binary search code, it is really easy to implement this expected functionality. You can compare the below implementation code with the binary search code; specially look at the three comments shown in both .

package com.digizol.puzzle;

public class MinimumDifferences {

    public int[] getMinPair(int[] sorted, int value) {
        if (sorted.length == 0) {
            return new int[] {};
        }
        return getMinPair(sorted, value, 0, sorted.length - 1, new int[]{});
    }

    private int[] getMinPair(int[] sorted, int value, 
                             int leftIndex, int rightIndex, int[] minValues) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return minValues;
        }

        // 2. middle index
        int middleIndex = (leftIndex + rightIndex) / 2;

        if (minValues.length == 0) {
            minValues = new int[] { sorted[middleIndex] };
        } else {
            int oldDiff = diff(value, minValues[0]);
            int newDiff = diff(value, sorted[middleIndex]);
            
            if (newDiff < oldDiff) {
                minValues = new int[] { sorted[middleIndex] };
            } else if (newDiff == oldDiff)  {
                int[] temp = minValues;
                minValues = new int[temp.length + 1];
                for (int i = 0; i < temp.length; i++) {
                    minValues[i] = temp[i];
                }
                minValues[minValues.length - 1] = sorted[middleIndex];
            }
        }

        // 3. recursive invoke
        if (sorted[middleIndex] > value) {
            return getMinPair(sorted, value, leftIndex, middleIndex - 1, minValues);
        } else if (sorted[middleIndex] < value) {
            return getMinPair(sorted, value, middleIndex + 1, rightIndex, minValues);
        } else {
            return minValues;
        }
    }

    private int diff(int value, int currentValue) {
        
        int diff = currentValue - value;
        if (diff < 0) {
            diff = -diff;
        }
        return diff;
    }
}

Two Arrays Problem

Now we have got the minimum distance number pairs against a given value. Now the enhancement is quite simple, just need to invoke the above "getMinPair(int[] sorted, int value)" method with each value in the second array of the problem and find the smallest minimum of those.

Test Cases

Following is one of the test cases to check this two array based implementation.

    @Test
    public void shouldReturnMultiplePairsIfFoundInGivenArrays() {
        int[] first = { 1, 10, 20, 30, 40};
        int[] second = { 6, 14, 25, 35, 45};
        int[][] result = sut.getMinPair(first, second);
        assertEquals(2, result.length);
        
        for (int i = 0; i < result.length; i++) {
            if (result[i][0] == 6) {
                assertEquals(10, result[i][1]);
            } else if (result[i][0] == 10) {
                 if (result[i][1] != 6 && result[i][1] != 14) {
                     assert false;
                 }
            } else if (result[i][0] == 14) {
                assertEquals(10, result[i][1]);
            }
        }
    }

You can insert the following method into the above implemented MinimumDifferences class to complete the implementation for the puzzle.

    public int[][] getMinPair(int[] first, int[] second) {
        int[][] pairs = new int[0][];
        
        int diff = Integer.MAX_VALUE;
         
        for (int i = 0; i < second.length; i++) {

            // invoke modified binary search method
            int[] mins = getMinPair(first, second[i]);
            
            if (mins.length != 0) {
                int localDiff = mins[0] - second[i];
                if (localDiff < 0) {
                    localDiff = -localDiff;
                }
                if (diff > localDiff) {
                    diff = localDiff;
                    pairs = new int[mins.length][2];
                    for (int j = 0; j < mins.length; j++) {
                        int[] value = new int[]{mins[j], second[i]};
                        pairs[j] = value;
                    }
                } else if (diff == localDiff) {
                    int[][] temp = pairs;
                    pairs = new int[temp.length + mins.length][2];
                    for (int j = 0; j < temp.length; j++) {
                        pairs[j] = temp[j];
                    }
                    for (int j = 0; j < mins.length; j++) {
                        int[] value = new int[]{mins[j], second[i]};
                        pairs[j + temp.length] = value;
                    }
                }
            }
        }
        return pairs;
    }

Hope this helps you to understand how binary search can be modified to solve two sorted arrays based problem.

Related Articles

• Java: Binary Search (recursive) & TestCases
• Java Sorting: Comparator vs Comparable Tutorial