Median in a Row-Wise Sorted Matrix

Medium
1390.

Median in a Row-Wise Sorted Matrix

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.

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 <= 400
  • R and C are odd
  • 1 <= mat[i][j] <= 2000
  • Each row of mat is sorted in non-decreasing order
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number}
 */
var median = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 400
  • R and C are odd
  • 1 <= mat[i][j] <= 2000
  • Each row of mat is sorted in non-decreasing order

Hints for Median in a Row-Wise Sorted Matrix

  1. Hint 1

    The median m is the smallest value such that at least (R · C + 1) / 2 elements are <= m.

  2. Hint 2

    For a guess x, counting the elements <= x takes one binary search per row because each row is sorted.

  3. Hint 3

    Binary-search x between 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

  1. Let lo be the minimum of the first column and hi the maximum of the last column; let need = (R · C) / 2 + 1.
  2. While lo < hi, take mid = lo + (hi - lo) / 2 and count the elements <= mid with an upper-bound binary search in each row.
  3. If the count is at least need, set hi = mid; otherwise lo = mid + 1.
  4. 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 + 1 in 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 lo

Java

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