Smallest Difference

Given two lists of positive integers, return the two numbers from each list that have the smallest absolute difference.

For example, in [-1, 5, 10, 20, 28, 3] and [26, 134, 135, 15, 17], the numbers with the smallest difference are [28, 26].

We could compare each item on one list to every other item on the next list and keep track of the current difference while recomputing the smallest difference and returning that. This however would turn out to take quadratic time. To do better, we can take advantage of the properties of a sorted array. This would take o(nlogn + mlogm) time where n and m are the lengths of both arrays, respectively. We can then use two pointers starting at index 0 for each array and iterate until we're at the end of either of the two. While iterating, we have to determine which index to increment as well as compute our current difference. If the value from array one is less than the value from array two, that means we should try to get closer to the value of array two - so here we increment index one. If arrayOne[idxOne] is more than arrayTwo[idxTwo], we must increment index two. Before the end of every iteration, we re-compute smallest difference. We'll also need a variable to track smallest pair, which can be mutated here as well.