DSA interview question

Median of a Row-Wise Sorted Matrix

Medium · Algorithms · Topics: binary search, matrix

The problem

A telemetry system stores readings from several sensors as a matrix: each row is sorted, but rows are independent. Analysts want the median of all readings without merging everything into one sorted list (which costs O(R·C log(R·C)) and a lot of memory). The trick is to binary-search on the value instead of on positions: for a candidate x, count how many readings are ≤ x using one binary search per row. The median is the smallest x for which that count exceeds half the total.

Example: [[1, 3, 5], [2, 6, 9], [3, 6, 9]] → 5 (sorted: 1, 2, 3, 3, 5, 6, 6, 9, 9).

Function signature

int matrixMedian(const vector<vector<int>>& mat);  // R x C, each row sorted, R * C odd

Test cases

Input `mat`	Output	Explanation
`[[1, 3, 5], [2, 6, 9], [3, 6, 9]]`	5	The 5th of 9 values
`[[1], [2], [3]]`	2
`[[1, 3, 8]]`	3	A single row
`[[1, 1, 3], [2, 2, 2], [3, 3, 3]]`	2	Sorted: 1, 1, 2, 2, 2, 3, 3, 3, 3
`[[5]]`	5

(Confirm: every row is sorted; the total number of elements is odd, so the median is a single element.)

How interviewers phrase it

"Find the median in a row-wise sorted matrix" (GeeksforGeeks, InterviewBit).
A good test of "binary search on the answer" where the answer is a value, not an index.

Clarifying questions to ask

Is R × C odd? (So the median is one element.)
Is each row sorted in non-decreasing order?
What's the value range? (It bounds the number of iterations.)

Follow-ups to expect

"What are you binary-searching?"
"How do you count elements ≤ x?"
"Why the smallest x with count > total / 2?"
"Why is the answer an element of the matrix?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview