O(n) time smallest spanning window combination of the elements in k sorted arrays

Question

Is there a way to get, in O(n) time, the combination of the elements in k sorted arrays which gives me the smallest difference between the minimum and maximum elements in the combination? n is the total number of elements in those arrays.

Here is an example:

array1 = [11]
array2 = [5,7]
array3 = [6,18]

And for those arrays, below are all possible combinations:

comb1 = [11, 5, 6]
comb2 = [11, 7, 6]
comb3 = [11, 5, 18]
comb4 = [11, 7, 18]

In this case, the differences of the minimum and maximum elements are 6, 5, 13, 11 respectively for the above combinations. So, what I should return is comb2, since the difference for that combination is the smallest.

In case it helps, there are no repeating elements in the entire set of values in the original arrays.

Answer 1

Sort the numbers together, as well as each array separately :

a: 11
b: 5, 7
c: 6, 18

5,  6,  7, 11, 18
b1 c1  b2  a1  c2

For any choice we make not to remove an outer number (the right- or left-most), the next sequence of choices is clear. If we choose to fix c2 (18), we can go up to b2 from the left. But if we remove c2, the only change in the left-bound is within the c array itself.

Start with the most we can remove from the left for the fixed rightmost element. At any point, removing an element from the right will only move the left-bound if the element is one of the last two in any one array. Keep removing the rightmost element, each time updating the left-bound if needed. Pick the best seen interval. (Note that the elements between the outer two elements do not matter, we can pick any one from each array as a representative.)

Complexity of the sliding window iteration after sorting is O(n) since with sorted arrays, the cumulative left-bound updates are O(n).