Median in a Row-Wise Sorted Matrix — Problem & Solution
Median in a Row-Wise Sorted Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Median in a Row-Wise Sorted Matrix is a medium coding problem on arrays, binary search and matrix, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Matrix
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
mat is an R x C matrix in which every row is sorted in non-decreasing order (columns need not be). Both R and C are odd, so the matrix holds an odd number of elements.
Return the median of all R · C elements: the value that would sit exactly in the middle if every element were written into one sorted list.
Try to do better than collecting and sorting all the elements.
Example 1
Input: mat = [[1,3,5],[2,6,9],[3,6,9]]
Output: 5
Explanation: All nine values sorted: 1, 2, 3, 3, 5, 6, 6, 9, 9 — the fifth is 5.
Example 2
Input: mat = [[1],[2],[3]]
Output: 2
Example 3
Input: mat = [[4,4,8]]
Output: 4
Constraints
1 <= R, C <= 400R and C are odd1 <= mat[i][j] <= 2000Each row of mat is sorted in non-decreasing order
Hints for Median in a Row-Wise Sorted Matrix
Hint 1
The median
mis the smallest value such that at least(R · C + 1) / 2elements are<= m.Hint 2
For a guess
x, counting the elements<= xtakes one binary search per row because each row is sorted.Hint 3
Binary-search
xbetween the smallest first-column value and the largest last-column value.
How to solve Median in a Row-Wise Sorted Matrix
Binary search on the value, not on positions. For a candidate x, the number of elements <= x is the sum over rows of an upper-bound search, and that count only grows with x; the median is the smallest x whose count reaches the middle rank.
Approach
- Let
lobe the minimum of the first column andhithe maximum of the last column; letneed = (R · C) / 2 + 1. - While
lo < hi, takemid = lo + (hi - lo) / 2and count the elements<= midwith an upper-bound binary search in each row. - If the count is at least
need, sethi = mid; otherwiselo = mid + 1. - Return
lo.
Why it works
Let m be the true median. Exactly need - 1 elements lie strictly in front of it in sorted order, so count(m) >= need while count(m - 1) < need. Because count is non-decreasing, m is the smallest value with count >= need, which is precisely what the search converges to — and it is always an actual element of the matrix.
Complexity
- Time —
O(R · log C · log V) with V the value range - Space —
O(1)
Pitfalls
- Count elements
<= mid(upper bound), not< mid, or duplicates around the median break the search. - The middle rank is
(R · C) / 2 + 1in 1-based terms — off by one here returns a neighbour. - Rows are sorted but columns are not, so the global minimum and maximum come from the first and last columns.
Reference solution
Python
from typing import List
import bisect
def median(mat: List[List[int]]) -> int:
rows, cols = len(mat), len(mat[0])
lo = min(row[0] for row in mat)
hi = max(row[-1] for row in mat)
need = rows * cols // 2 + 1
while lo < hi:
mid = (lo + hi) // 2
cnt = 0
for row in mat:
cnt += bisect.bisect_right(row, mid)
if cnt >= need:
hi = mid
else:
lo = mid + 1
return loJava
public static int median(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int[] row : mat) {
lo = Math.min(lo, row[0]);
hi = Math.max(hi, row[cols - 1]);
}
int need = rows * cols / 2 + 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int[] row : mat) {
int a = 0, b = cols;
while (a < b) {
int m = (a + b) >>> 1;
if (row[m] <= mid) a = m + 1; else b = m;
}
cnt += a;
}
if (cnt >= need) hi = mid; else lo = mid + 1;
}
return lo;
}C++
int median(vector<vector<int>>& mat) {
int rows = mat.size(), cols = mat[0].size();
int lo = INT_MAX, hi = INT_MIN;
for (auto& row : mat) {
lo = min(lo, row[0]);
hi = max(hi, row[cols - 1]);
}
int need = rows * cols / 2 + 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (auto& row : mat) cnt += upper_bound(row.begin(), row.end(), mid) - row.begin();
if (cnt >= need) hi = mid; else lo = mid + 1;
}
return lo;
}JavaScript
var median = function(mat) {
var rows = mat.length, cols = mat[0].length;
var lo = mat[0][0], hi = mat[0][cols - 1];
for (var i = 1; i < rows; i++) {
if (mat[i][0] < lo) lo = mat[i][0];
if (mat[i][cols - 1] > hi) hi = mat[i][cols - 1];
}
var need = Math.floor(rows * cols / 2) + 1;
while (lo < hi) {
var mid = lo + ((hi - lo) >> 1);
var cnt = 0;
for (var r = 0; r < rows; r++) {
var a = 0, b = cols;
while (a < b) {
var m = (a + b) >> 1;
if (mat[r][m] <= mid) a = m + 1; else b = m;
}
cnt += a;
}
if (cnt >= need) hi = mid; else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search