Coding

Matrix Median

Asked at

J.P. Morgan

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a 2D array **matrix **that is row-wise sorted. The task is to find the median of the given matrix.

Input: matrix=[ [1, 4, 9], [2, 5, 6], [3, 7, 8] ] Output: 5 Explanation: If we find the linear sorted array, the array becomes 1 2 3 4 5 6 7 8 9. So, median = 5

Input: matrix=[ [1, 3, 8], [2, 3, 4], [1, 2, 5] ] Output: 3 Explanation: If we find the linear sorted array, the array becomes 1 1 2 2 3 3 4 5 8. So, median = 3

Input: matrix=[ [1, 4, 15], [2, 5, 6], [3, 8, 11] ]

N==matrix.size
M==matrix[0].size
1 <= N, M <= 105
1 <= N*M <= 106
1 <= matrix[i] <= 109
N*M is odd

cpp

class Solution{
public:
    int findMedian(vector<vector<int>>&matrix) {
      
    }
};

java

class Solution {
    public int findMedian(int[][] matrix) {
      
    }
}

python

class Solution:
    def findMedian(self, matrix):

javascript

class Solution {
    findMedian(matrix) {
       
    }
}

csharp

class Solution {
    public int FindMedian(List<List<int>> matrix) {

    }
}

func findMedian(matrix [][]int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Search the value range, not coordinates.
02For a midpoint, count elements less than or equal to it in each row.
03Use upper bound within every sorted row.
04Move low or high based on the target rank.
05Return the first value with sufficient count.

Reference answer

The median is the element at rank (R*C)/2 in zero-based order, so binary search possible values between the smallest row head and largest row tail. For a midpoint mid, count how many matrix elements are <= mid; because each row is sorted, use upper_bound in each row rather than scan it. If the count is at most the target rank, the median is larger, otherwise it is at most mid. Continue until low == high; that first value with count greater than the rank is the median. This works without globally sorting the matrix because the count predicate is monotonic in mid. Runtime is O(R log C log V) and extra space is O(1), where V is the numeric range.

Then expect these follow-ups

How would a heap-based solution compare?
Tests: tradeoffs
How do duplicates affect the predicate?
Tests: binary-search correctness

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question