Given two arrays of integers, find the pair of values with the smallest difference.

Overview

Naive Solution

This can be easily solved by using two for loops and going through each number in both arrays and keeping track of the smallest difference. This would have a quadratic O(n^2) time complexity.

If the arrays are large, finding the solution can take too long, there is a more optimal solution.

Optimal Solution

Flow Diagram

It is important to note, that sorting the array first as part of the algorithm allows us to reach an optimal solution.

Time Complexity

Time complexity is O(Nlog(n)) + O(Mlog(m)). Because we are sorting the both arrays first and then iterating through both arrays once in a while loop. N is the length of the first array and M is the length of the second array.

Space Complexity

No extra space is needed for this algorithm, which is great. This gives us constant time O(1)

Java Source Code

    public int[] find(int[] arrayOne, int[] arrayTwo) {
        Arrays.sort(arrayOne);
        Arrays.sort(arrayTwo);

        var indexArrayOne = 0;
        var indexArrayTwo = 0;
        var smallestDiff = Integer.MAX_VALUE;
        var currentDiff = Integer.MAX_VALUE;
        var smallestPair = new int[0];
        final var arrayOneLength = arrayOne.length;
        final var arrayTwoLength = arrayTwo.length;

        while(indexArrayOne < arrayOneLength && indexArrayTwo < arrayTwoLength) {
            int firstNum = arrayOne[indexArrayOne];
            int secondNum = arrayTwo[indexArrayTwo];

            if(firstNum < secondNum) {
                currentDiff = secondNum - firstNum;
                indexArrayOne++;
            } else if(secondNum < firstNum) {
                currentDiff = firstNum - secondNum;
                indexArrayTwo++;
            } else {
                return new int[]{firstNum,secondNum};
            }

            if(smallestDiff > currentDiff) {
                smallestDiff = currentDiff;
                smallestPair = new int[]{firstNum,secondNum};
            }
            }

            return smallestPair;
        }
      }

Conclusion

When you go in search of honey you must expect to be stung by bees.

Joseph Joubert