Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N)

Question

Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N).

Another variant of the question goes like this: given a matrix with sorted rows, and sorted columns, find kth smallest.

We can easily formulate an O(klogk) solution with minheap, but the challenge is doing the same in O(N) time ...

The paper below formulates the solution but I could not understand it. Can somebody explain it or any alternative idea?

hint: http://www.cse.yorku.ca/~andy/pubs/X%2BY.pdf

Answer 1

Let's go with this formulation:

Another variant of the question goes like this: given a matrix with sorted rows, and sorted columns, find K^th smallest.

Let M(1,1) denote the corner of the matrix with the smallest number and let M(n,n) be the corner with the highest number. (obviously they both are on the same diagonal of M).

Now let's think of sub-matrices: if we take the sub-matrix ranging from M(0,0) to M(p,p) we get a matrix that has the p^2 smallest value at position M(p,p) and all its other values are smaller. AND the fields M(0,p)-M(p,p) and M(p,0)-M(p,p) taken together consist of 2p-1 values.

So we only look at these values:

because we know for sure that the K^th smallest value is in there.

So your desired algorithm boils down to (pseudocode):

p := ceil( sqrt(K) )
candidate_list := merge (M(*,p), M(p,*)) // this has O(p) runtime since both lists are sorted
kth_element := candidate_list[p^2 - k] // +1 if your list starts at 1. 

Since the first and last row have runtime O(1) the total runtime is

O(p) <= O(sqrt(k)+1) <= O(sqrt(n^2)+1) <= O(n+1) <= O(n)

Answer 2

If you have a pair of numbers a[i] and b[j] then the next value will be a[i+1] + b[k] with k<=j or a[k] + b[j+1] with k <= i.

This means that you can get the next number by:

int newI = i+1;
int newJ = j;
for(;newJ>=0 && a[i]+b[j]<a[newI]+b[newJ];newJ--){}
int newI2 = i;
int newJ2 = j+1;
for(;new2I>=0 && a[i]+b[j]<a[new2I]+b[new2J];new2I--){}
if(a[new2I]+b[new2J]<a[newI]+b[newJ])
    //new2I and new2J are the next values
else
    //newI and newJ are the next values

You do this K times, it's not O(n) though.