How do you find median in a 2D sorted array?

Question

Lets say you have a Matrix of numbers that are sorted across rows as well as column.

How do you find the median.

I searched on net and found lot of answers like:

There is an algorithm to find median of two sorted arrays in O(logn)- apply this n times. I don't think that it makes any sense.

Or else I get some research papers. The problem does not seem that jazzy though.

Can anyone give me a precise algorithm?

So essentially you have something like: ((1, 3, 5), (2, 6, 9), (4, 10, 14)), that is sorted both row-wise and column-wise? — aaaaaa123456789, Feb 10 '13 at 10:41
Link to the `"algorithm to find median of two sorted arrays ..."`? — Bernhard Barker, Feb 10 '13 at 10:50
I think the question you want to ask is 'Given a N cross M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd. Note: No extra memory is allowed.' — Achyut Rastogi, Dec 24 '16 at 13:16
Possible duplicate of [Median of a Matrix with sorted rows](https://stackoverflow.com/questions/41414421/median-of-a-matrix-with-sorted-rows) — roottraveller, Jul 30 '17 at 18:46

score 0 · Answer 1 · answered Oct 15 '16 at 06:54

Given it's a row wise and column wise sorted matrix (m x n), we can find the median in O(m*n*log(m)) using Priority Queue.

The pseudocode is,

PriorityQueue<Pair<int, int>> pq(m); 
//Pair<int, int> is the coordinate of the matrix element
for i <- 0 to m
    pq.add(Pair(i, 0))
count <- 0
k = (m*n)/2
Pair<int, int> xy
while count < k:
    count++
    xy <- pq.poll()
    x <- xy.first
    y <- xy.second
    if y+1 < n:
        pq.add(Pair(x, y+1))
return matrix[xy.first][xy.second]

How do you find median in a 2D sorted array?

1 Answers1