Finding the k-th smallest ternary sum of elements from three different arrays

Question

The problem goes like this:

Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+b_s+c_t$ where $r, s, t$ are arbitrary indices.

Since $k$ is relatively much smaller than $n^3$ (we may suppose $k \approx n $ for simplicity), it would be wasteful to: naively enumerate all $n^3$ possibilities and find the $k-$th smallest using a binary heap.

What is a more efficient way (in terms of time complexity) to solve this problem? I try to optimize the naive algorithm described above by first sorting three arrays then do the heaping for $\{ a_r + b_s + c_t: r+s+t < k \}$, but I believe this is far from a most efficient algorithm. Thanks.

(Rmk: the algorithm is intended to be comparison-based, since elements might be non-integers.)

Answer 1

You can first sort the three arrays. In the following answer we assume these arrays are already sorted.

You can maintain a priority queue $Q$. Initially it contains only $a_0+b_0+c_0$. Then in each iteration, you pop the smallest element (say $a_r+b_s+c_t$), and add $a_{r+1}+b_s+c_t$, $a_r+b_{s+1}+c_t$ and $a_r+b_s+c_{t+1}$ (duplicates are not allowed, while it is easy to check whether a combination already exists in $Q$). Now we can claim the popped sum in the $i$-th iteration is the $i$-th smallest sum.

This algorithm takes $O(n\log n)$ time. If the given three arrays are already sorted, the time is reduced to $O(k\log k)$.

We can use mathematical induction on $i$ to prove the correctness. Suppose the $i$-th smallest sum is $a_r+b_s+c_t$, then we have the following chain:

\begin{align} &a_0+b_0+c_0\\ \le\ &a_1+b_0+c_0 \\ \le\ &\cdots \\ \le\ &a_r+b_0+c_0 \\ \le\ &a_r +b_1+c_0 \\ \le\ &\cdots \\ \le\ &a_r +b_s+c_0 \\ \le\ &\cdots \\ \le\ &a_r+b_s+c_t. \end{align}

For convenience, we denote by $S_0,\ldots,S_{\ell}$ these sums in the chain. Let $S_j$ be the first sum in the chain that is not popped before the $i$-th iteration. Then in the iteration that $S_{j-1}$ is popped, $S_j$ is added to $Q$ according to our algorithm. This means the sum popped in the $i$-th iteration must be no more than $S_j$, thus no more than $S_{\ell}=a_r+b_s+c_t$. By inductive assumption, the first $i-1$ smallest sums are popped before the $i$-th iteration, so the sum popped in the $i$-th iteration is exactly the $i$-th smallest sum.

Answer 2

I haven't tried to implement it but how about making 3 new arrays say A[k],B[k] and C[k] . These array would store the k smallest elements of all individual predefined arrays and would take O(N) time here N is the number of elements the biggest array, To sort these array we could use the heap sort incurring - O(klogk) time complexity.

initialise a new array - result[K]

now the following loops won't take more than O(k) time.

int a=0,b=0,c=0; variables for indices to the array

for(i in range (0,k-1)) {

result[i]=A[a]+B[b]+C[c];

select smallest amongst A[a+1],B[b+1],C[c+1]; -(let's say A[i+1] is smallest)

increment the variable to the array which has been found to be the smallest in the previous step(here, a=a++;)

}

the ith element of the array would contain the ith smallest integer in the combinations of the array. The worst case time complexity would also be just O(n+klogk). Hope this helps you :) Let me know if I could assist you further.