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

Answer 2

With the matrix given in the example: If you want to search for the 7-th element, you know the 7-th element is in the elements M[4][1..4], M[1..4][4]. You obtain two arrays already sorted, 12,14,15,20 and 11,17,19 which can be merged. Then you apply a binary search which is O(log N).

Generalize: for k-th biggest element in this matrix, you have to select the proper layer: [2N-1] + [2(N-1)-1]+...>=k so the algorithm to select the proper layer to lookout for is Sum[2(N-i)-1]>=k, for i=0,N-1, where i is the layer's number. After you find i, the layer number, you will have 2(N-i)-1 elements in that array that have to be merged and then searched. The complexity to search that layer is O(log[2(N-i)-1] = O(log(N-i))...

The arithmetic progression leads to

0>=i^2-2*N*i+k

i1,2=N+-sqrt(N^2-k), where k is the element we search...