Find kth largest element from a 2-d sorted array

Problem

Given the 2D matrix or array - sorted row-wise and column-wise, find the kth largest element.

Example

Input
Consider the array below and k=4

 1   2   3   4   5
 6   7   8   9  10
11  12  13  14  15
16  17  18  19  20
21  22  23  24  25

Output
Output should be 22

Solution

Method 1 - Use MaxHeaps
We know if k=1, we should return A[n-1][n-1] i.e. the last element of the array. So, we have to give the kth largest, so we have to start from the end of the array, and keep on selecting the max element adjacent to the last one, and maintain the history of max elements, once we traverse to the next element.

Here is how we should go:

1. Create a max-heap
2. Insert the last element of each row in the heap and do heapify for each inserted element
3. Repeat steps 5,6&7 for k-1 times then go to step-8
4. Extract-max element from the heap
5. Insert the elements adjacent to the current element, (and do heapify) from the row to which the extracted element corresponds to..
6. Heapify for newly inserted element
7. Now Extract the largest element from the heap and this will be the required answer, number of elements extracted are equal to k.

Here is the pseudocode

Push A[n-1][n-1] in the heap.

for i = 1 to k
    curr_element = pop max element from heap
    Push the right and bottom neighbor of the popped element from the matrix
        (if they exist and have not been pushed earlier)

return curr_element

Time complexity = loop runs k times (O(k)) * 1 iteration runs O(3*log(k)) times = O(k*log(k))

References

• http://stackoverflow.com/questions/5940420/find-kth-largest-element-from-a-2-d-sorted-array
• http://learn.hackerearth.com/forum/161/kth-largest-element-in-a-2d-array-sorted-along-both-rows-and-columns/