Selection algorithms on sorted matrix

Question

this is a google interview question :

Given a N*N Matrix. All rows are sorted, and all columns are sorted. Find the Kth Largest element of the matrix.

doing it in n^2 is simple and we can sort it using heap or merge sort (n lg n) and then get it, but is there a better approach, better than (n lg n)?

example of the array ::

 1   5   7  12
 3   6   8  14
 4   9  10  15
11  17  19  20

1<5<7<12 and 1<3<4<11 similarly the other rows and columns. now say we need to find the 10th smallest element, in here it is 11..hope this adds some detail to the question...

Answer 1

Yes, there is an O(K) algorithm due to Frederickson and Johnson.

Greg N. Frederickson and Donald B. Johnson. Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13, pp. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no