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

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?

• Pro Tip: If you're posting from a cell phone, most modern phones have a setting that will capitalize `I` and your sentences automatically. Mar 20, 2014 at 19:30

Let's go with this formulation:

Another variant of the question goes like this: given a matrix with sorted rows, and sorted columns, find Kth 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 Kth 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)
``````
• 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. Mar 21, 2014 at 13:11
• 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. Mar 23, 2014 at 18:40
• @masgo The recursion is on an input of half size, so the running time is linear by the Master Theorem. Apr 23, 2014 at 16:56

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.