Find kth largest element from a 2-d sorted array

Question

I have a 2 dimensional array. The rows and columns are sorted. How to find the kth largest element from the 2-d array?

Answer 1

If you have an n * n matrix then it is possible to do this in average time O(n * log(n) * log(n)).

What you do is break the matrix into a series of sorted arrays, then do a binary search through all of them at once. For instance suppose that n = 4 and is indexed from (0,0) to (3,3). We can break it into arrays that go down a column to the rising diagonal then turn right to finish the row. This would give us the following set of sorted arrays:

1. (0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3)
2. (1,0), (1,1), (1,2), (2,2), (3,2)
3. (2,0), (2,1), (3,1)
4. (3,0)

This gives us n sorted lists out of the matrix.

So we need to figure out where the k'th element is in a set of sorted arrays.

We will do this with a binary search for what its value should be.

Start by taking the midpoint of our longest array, which would be the element (0,3) in the example. Then for every other array figure out how many are bigger than, smaller than, or equal to this value. (You can find this by a binary search.) This let's us figure out which side of that divide the k'th element is on. If it matches the element we just chose, we have the answer. Otherwise we can throw away on average half of each array (sometimes throw away whole arrays) and repeat.

After an average O(log(n)) operations, each of which costs O(n log(n)) to perform, we'll have the answer, leading to my estimate above.