1

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

1
  • 1
    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

2 Answers 2

3

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:

enter image description here

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)
3
  • 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.
    – CyberBoy
    Mar 21, 2014 at 13:11
  • 1
    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.
    – masgo
    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
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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