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.
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(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(p,0)-M(p,p) taken together consist of
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)