Find the Median of All Elements in a Row-Sorted Matrix

Hard25–30 min

Topics

ArrayMatrixBinary Search

Companies

AmazonMicrosoft

Given a matrix with an odd number of elements, where every row is individually sorted in ascending order, return the median of all the elements combined. Solve it without sorting the whole matrix: binary-search over the range of possible values rather than positions. For each candidate value, count how many elements are ≤ it (a per-row binary search, since rows are sorted) — the smallest value whose count passes the halfway mark is the median.

Test Case 1:

Input:matrix = [[1,3,5],[2,4,6],[3,5,7]]

Output:4

Explanation:Flattened and sorted: [1,2,3,3,4,5,5,6,7] — the middle (5th) value is 4.

Test Case 2:

Input:matrix = [[1, 2, 3]]

Output:2

Explanation:A single sorted row — the median is just its middle element.

Test Case 3:

Input:matrix = [[5]]

Output:5

Explanation:A single element is trivially its own median.

Constraints

◆1 ≤ matrix.length, matrix[0].length ≤ 100
◆matrix.length × matrix[0].length is odd (so the median is a single element, never an average)
◆-10⁵ ≤ matrix[i][j] ≤ 10⁵
◆Every row is sorted in ascending order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

matrix (rows separated by ;) — rows × cols must be odd, each row sorted ascending

1	class Solution {
2	public int matrixMedian(int[][] matrix) {
3	int rows = matrix.length, cols = matrix[0].length;
4	int lo = matrix[0][0], hi = matrix[0][cols - 1];
5	for (int i = 1; i < rows; i++) {
6	lo = Math.min(lo, matrix[i][0]);
7	hi = Math.max(hi, matrix[i][cols - 1]);
8	}
9	int half = (rows * cols) / 2;
10	while (lo < hi) {
11	int mid = lo + (hi - lo) / 2;
12	int count = 0;
13	for (int i = 0; i < rows; i++) {
14	int rlo = 0, rhi = cols;
15	while (rlo < rhi) {
16	int rmid = rlo + (rhi - rlo) / 2;
17	if (matrix[i][rmid] <= mid) rlo = rmid + 1; else rhi = rmid;
18	}
19	count += rlo;
20	}
21	if (count <= half) {
22	lo = mid + 1;
23	} else {
24	hi = mid;
25	}
26	}
27	return lo;
28	}
29	}
30

Variables

lo1

hi7

half4

INITIALIZE

Binary search over the VALUE range [1, 7] (not indices): for a candidate value mid, count how many elements across all rows are ≤ mid using each row's upper bound. Converge to the smallest value whose count passes half=4.

Step 1 / 5

Approach & Solutions

Brute Force — Flatten, Sort, Pick the Middle

Brute

Copy every element into one array, sort it, and read off the middle value — exactly what "median" means by definition. Correct, but it throws away the fact that every row arrives pre-sorted, which is exactly the structure "binary search on the answer" needs to avoid the full sort.

TimeO(R·C log(R·C))

SpaceO(R·C)

Java

Try it out

class Solution {
    public int matrixMedian(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] flat = new int[rows * cols];
        int idx = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                flat[idx++] = matrix[i][j];
            }
        }
        Arrays.sort(flat);
        return flat[flat.length / 2];
    }
}

Optimal — Binary Search on the Answer's Value

Optimal

Instead of searching for an index, binary-search over the range of possible median *values*. For a candidate value mid, count how many elements across the whole matrix are ≤ mid — each row contributes that count in O(log C) via an upper bound, since the row is sorted. If that count doesn't yet exceed half the matrix, the true median must be bigger; otherwise it's mid or smaller. Converge to the smallest value where the count finally passes the halfway mark — that value is the median.

TimeO(R log(maxVal - minVal) · log C)

SpaceO(1)