TL;DR I don't think that this is possible to do in O(n)
(though I cannot prove it), so below you can find two O(n*logk)
solutions.
Solution 1:
Use min-heap of size k
as described here.
Solution 2 (mine)
We need 3 additional arrays, let's call them A
, B
and C
. Let's also call the input arrays "original arrays".
A
will have size n
and will keep all elements from all original arrays in sorted order
B
will also have size n
and will keep information about the source of the elements in the array A
, i.e. from which original array element in A
comes from
C
will have size k
and it will contain last seen indices of elements from the original arrays during the process (see below)
Because the original arrays are sorted, we can create arrays A
and B
in O(n*logk)
time by using k-way merge algorithm (one example is with min-heap: at the beginning put first elements of all original arrays in min heap; then iteratively pop the smallest element from the min heap, put in B
, and push the next element from the same original array in heap). So, for the example you provided, arrays A
and B
will look like this: A = [5, 6, 7, 11, 18], B = [1, 2, 1, 0, 2]
(5
comes from second original array, 6
comes from third original array etc.).
Now we use sliding windows technique to find the window of size at least k
whose difference between last and first element is the smallest. The idea is to iterate through array B
until we "collect" elements from all original arrays - it means that we found a combination, and now just check the difference between the first and last element of that combination. Array C
now comes in the game - we initialize all its elements with -1, and set C[i]
to last index of any element from the original array i
. Once we find first sliding window that contains elements from all original arrays, we further extend that window to the right and shrink from the left while keeping the property that representatives from all original arrays are inside the window. So, algorithm will look like this:
// create arrays A and B, initialize array C
int collected = 0;
int min_idx = 0;
int result = INT_MAX;
for (int i = 0; i < n; ++i) {
bool check_result = false;
if (C[B[i]] == -1) {
++collected;
check_result = true;
}
C[B[i]] = i;
while (min_idx < C[B[min_idx]] && min_idx < i) {
check_result = true;
++min_idx;
}
if (collected < k) continue;
if (check_result && result > (A[i] - A[min_idx]))
result = (A[i] - A[min_idx]);
}
return result;
Let's explain it through your example:
A = [5, 6, 7, 11, 18]
B = [1, 2, 1, 0, 2]
C = [-1, -1, -1]
i = 0 // state after step 0, we have seen element from array 1
min_idx = 0
C = [-1, 0, -1]
collected = 1
result = INT_MAX
i = 1 // we have seen element from array 2
min_idx = 0
C = [-1, 0, 1]
collected = 2
result = INT_MAX
i = 2 // again element from array 1, increase min_idx
min_idx = 1
C = [-1, 2, 1]
collected = 2
result = INT_MAX
i = 3 // element from array 0, window is full, update result
min_idx = 1
C = [3, 2, 1]
collected = 3
result = 5
i = 4 // again element from array 2, increase min_idx and compare with result -> it is bigger, so don't update result
min_idx = 2
C = [3, 2, 4]
collected = 3
result = 5
Time complexity is O(n*logk)
because creating arrays A
and B
from k
sorted arrays takes O(n*logk)
, and during the loop each of n
elements is checked at most twice so this part is O(n)
and finally O(n*logk + n) = O(n*logk)
. If you merge original arrays into one, this is the best you can get:
One can show that no comparison-based k-way merge algorithm exists
with a running time in O(n f(k)) where f grows asymptotically slower
than a logarithm.
Hope this helps!
k
is constant. Ifk
is some small or constant number,k*n
or(logk)*n
is stillO(n)
.