Fastest algorithm for finding first k elements in ordered cross sums of two sorted arrays

Question

I have two sorted arrays x[] and y[] of floats. The array sizes are n and m respectively.

I need to find the ordered k-th, k << min(m, n), element in the array of cross sums, i.e. s = {x[0] + y[0], x[0] + y[1], ..., x[0] + y[m-1], x[1] + y[0], x[1] + y[1], ..., x[1] + y[m-1], ..., x[n-1] + y[0], x[n-1] + y[1], ..., x[n-1] + y[m-1]}.

My current method is more or less to concatenate the arrays of

{x[0] + y[0], x[0] + y[1], ..., x[0] + y[m-1]},

{x[1] + y[0], x[1] + y[1], ..., x[1] + y[m-1]},

...

{x[k-1] + y[0], x[k-1] + y[1], ..., x[k-1] + y[m-1]},

{y[0] + x[0], y[0] + x[1], ..., y[0] + x[n-1]},

{y[1] + x[0], y[1] + x[1], ..., y[1] + x[n-1]},

...

{y[k-1] + x[0], y[k-1] + x[1], ..., y[k-1] + x[n-1]},

and then select the k-th element.

What's the fastest way to achieve it?

Answer 1

Here's a python implementation of the algorithm @Jetunsaure proposed. It does the minimal amount of addition necessary to compute the final result:

def kth_smallest_sum(x, y, k):
    row = min_row = 0
    max_row = len(x)
    max_col = len(y)
    indexes = [0] * max_row
    for _ in range(k):
        msum = None
        for r in range(min_row, min(row+2, max_row)):
            c = indexes[r]
            tsum = x[r] + y[c]
            if msum is None or tsum < msum:
                minr, msum = r, tsum
        ksum = msum
        if indexes[minr] == max_col - 1:
            min_row += 1
        else:
            indexes[minr] += 1
        row = max(row, minr)
    return ksum

Sample usage:

kth_smallest_sum([i * 7 for i in range(10)], [i * 5 for i in range(10)], 8)

Output:

17

Update

I modified the original code to support k values greater than min(len(x), len(y) (see above). I then ran performance testing on this and @DillonDavis solution, using x, y data pf lengths 100, 100; 10, 1000; and 1000, 10 with k ranging from 1 to 8192 in powers of 2. The testing code was this:

random.seed('kth')
for N, M in [(10, 1000), (100, 100), (1000, 10)]:
    x = sorted(random.sample(range(N*5), N))
    y = sorted(random.sample(range(M*5), M))
    
    out = perfplot.bench(
        setup=lambda n:n,
        kernels = [lambda n: find_kth_smallest(x, y, n), lambda n:kth_smallest_sum(x, y, n)],
        n_range = [2**x for x in range(13)],
        labels = ['heap', 'list']
    )
    out.save(f'{N}x{M}.png')

The results were as follows. As can be seen the heap performance is fairly constant (consistent with O(k log k)) where the list performance is affected by the size of the lists (consistent with O(k min(N,M))

100x100:

10x1000:

1000x10: