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]);
}
}
}
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;
}
Test cases for Binary search might not be something you have already written, but the implementation must be an old exercise you may have done in your algorithm lessons. May be it is easy for you to write it yourself without referring to examples or helping materials? I think it's time for you to try it yourself if you have not done it 
Initial part of finding second highest frequency characters in a text was discussed previously and covered the scenarios where a single character is the most frequent. Since this is the continuation post of that, I strongly recommend you to read the 
Finding second highest frequency character in a text is last weeks Thursdays Dzone Code Puzzle. Intention of this post is to try and work out this interview oriented problem in Java with you by explaining the way I am approaching this task. In return, both you and myself can learn through a discussion. 
