Find Pair With Smallest Difference - Java Solution

1. Introduction

In this blog post, we'll explore a common algorithmic challenge - finding the pair of values, one from each of two unsorted arrays, that have the smallest (non-negative) difference. This problem is a good exercise in sorting and efficient searching.

Problem

Given two non-empty arrays of integers, the task is to find the pair of values (one value from each array) with the smallest (non-negative) difference.

Example:

Input: [1, 3, 15, 11, 2], [23, 127, 235, 19, 8]

Output: [11, 8]; this pair has the smallest difference.

2. Solution Steps

1. Sort both arrays to ensure efficient comparison.

2. Initialize pointers for each array, starting at the beginning.

3. Traverse both arrays and at each step, compute the difference between the elements pointed to by the pointers.

4. Keep track of the pair with the smallest difference found so far.

5. Move the pointer of the array that has the smaller element to the next position.

6. Repeat the process until the end of one of the arrays is reached.

7. Return the pair with the smallest difference.

3. Code Program

import java.util.Arrays;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 15, 11, 2};
        int[] arr2 = {23, 127, 235, 19, 8};
        int[] result = smallestDifference(arr1, arr2);
        System.out.println("Pair with the smallest difference: " + Arrays.toString(result));
    }

    // Method to find the pair with the smallest difference
    public static int[] smallestDifference(int[] arr1, int[] arr2) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int i = 0, j = 0;
        int smallestDiff = Integer.MAX_VALUE;
        int currentDiff;
        int[] smallestPair = new int[2];

        while (i < arr1.length && j < arr2.length) {
            int firstNum = arr1[i];
            int secondNum = arr2[j];

            // Compute the difference and update the smallest pair if necessary
            if (firstNum < secondNum) {
                currentDiff = secondNum - firstNum;
                i++;
            } else if (secondNum < firstNum) {
                currentDiff = firstNum - secondNum;
                j++;
            } else { // The numbers are equal
                return new int[] {firstNum, secondNum};
            }

            if (smallestDiff > currentDiff) {
                smallestDiff = currentDiff;
                smallestPair[0] = firstNum;
                smallestPair[1] = secondNum;
            }
        }

        return smallestPair;
    }
}

Output:

Pair with the smallest difference: [11, 8]

Explanation:

The input arrays are [1, 3, 15, 11, 2] and [23, 127, 235, 19, 8]. 

After sorting, the method smallestDifference checks each pair of elements from the two arrays, keeping track of the pair with the smallest difference. The pair [11, 8] is found to have the smallest difference in this case. 

The algorithm efficiently finds the pair with minimal difference by sorting the arrays first and then traversing them linearly.