2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Can you solve this for the case of two arrays? $\endgroup$ – Yuval Filmus Dec 23 '18 at 8:15
  • $\begingroup$ If you look for the k- smallest sum and the arrays are sorted, let j = ceil (k^(1/3)). Then aj + bj + cj >= the third smallest sum; that should help. Let I = ceil(k^(1/2)), then ai + bi + c0, ai + b0 + ci, a0 + bi + ci are all >= the third smallest element. $\endgroup$ – gnasher729 Dec 23 '18 at 10:28
  • $\begingroup$ "the algorithm is intended to be comparison-based". This cannot hold in the sense that a total order of all elements in three arrays cannot be even determine the second smallest combination. Some arithmetic such as additions should be used. $\endgroup$ – Apass.Jack Dec 23 '18 at 13:52
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Please take some time to edit and format your answer. I can hardly understand it. $\endgroup$ – xskxzr Dec 23 '18 at 8:50
  • $\begingroup$ thanks for letting me know, Some parts of the code was automatically hidden I don't understand why. Anyway have updated it a bit so that it's understandable. Let me know if this helps :) $\endgroup$ – Anonymous Developer Dec 23 '18 at 8:56
  • $\begingroup$ Your algorithm seems wrong. Suppose the arrays are all [0,1], then you first select 0+0+0, then 1+0+0, then 1+1+0, which is wrong (it should be 0+1+0). $\endgroup$ – xskxzr Dec 23 '18 at 9:30
  • $\begingroup$ It wasn't particularly mentioned in the question if numbers can be duplicate. I was assuming that numbers are all unique that's how you can call something like kth smallest. Anyway minor fixes can help here. It isn't required to fully change the algorithm. Just some fixes down in the loop where checking is done could treat this problem. However since you are much more experienced than I am thereby I assume it would be better to take your advice here :). $\endgroup$ – Anonymous Developer Dec 23 '18 at 9:38
  • $\begingroup$ To add it I would say if you have elements 0,1,1,1,2,3 then 3rd smallest would be 1 or 2? My entire algorithm would say it to be 2 because 0>1>2. Now that is something I guess where we are having different perceptions. Are you sure mine is incorrect ? talking specifically about the question and not in general. $\endgroup$ – Anonymous Developer Dec 23 '18 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.