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

• Robert Harvey: Pro Tip: If you're posting from a cell phone, most modern phones have a setting that will capitalize I and your sentences automatically.

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:

enter image description here

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)

• CyberBoy: well, i do not think "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". e.g consider M[0,p], so M[0,p+1] > M[0,p] and M[1,p] > M[0,p] but cannot draw any relation between diagonal elements, M[0,p+1] and M[1,p], can we? so we can say element at M[p][p] has "atleast" (p+1)^2-1 values lesser than itself but not anything else. Correct me if I am wrong.
• masgo: I have thought about it, and realized that you are right. My solution works only if the diagonals are also sorted. I also looked at the Paper you provided. I am not sure that their algorithm is in O(N). Take a look at Theorem 6.1: They state that biselect is in O(n). But biselect needs O(1/2 (n+1)) time just to build/filter the submatrix A-dash of A (Fig. 2, line 3. Section 2 explains what A-dash means). And then you have the recursion part. I am not completely certain, but I think biselect has O(n log n) runtime.
• David Eisenstat: @masgo The recursion is on an input of half size, so the running time is linear by the Master Theorem.

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.