Median of a Row-Wise Sorted Matrix

80.2k
0

Given a row-wise sorted matrix mat, find the median of all elements in the matrix.Each row is sorted in non-decreasing order. The total number of elements is odd, so the median is the exact middle element after all matrix values are arranged in sorted order.

Example 1

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

Output: 5

Explanation: If we store all elements in a single sorted array, it looks like [1, 2, 3, 3, 5, 6, 6, 9, 9]. The middle element of this array is 5, which is the median.

Example 2

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

Output: 3

Explanation: If we flatten and sort all elements, we get [1, 2, 3, 3, 3, 3, 4, 5, 6]. The middle element of this array is 3, which is the median.

Brute Force Approach

The most direct thought is to collect every element into one list, sort that list, and return the middle element. This works because the median is defined using the fully sorted order of all values, not the matrix shape.

Algorithm

  • First, create an empty list to store all matrix values in one place. This is needed because sorting row by row separately does not give the global sorted order.

  • Traverse every row and every column, and push each value into that list so no matrix element is missed.

  • Sort the full list because the median is defined from the complete sorted order of all elements.

  • Find the middle index using size / 2. This works because the total number of elements is odd, so there is one exact middle position.

  • Return the value stored at that middle index because that is the matrix median.

Dry Run

Matrix Median Brute Dry Run

Matrix Median Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the median value
of the row-wise sorted matrix.
*/
int median(vector<vector<int>>& mat) {
vector<int> values;
for (int i = 0; i < (int)mat.size(); i++) {
for (int j = 0; j < (int)mat[i].size(); j++) {
values.push_back(mat[i][j]);
}
}
// Sort all values because the median depends on global sorted order.
sort(values.begin(), values.end());
// This points to the exact middle because the total count is odd.
int middleIndex = (int)values.size() / 2;
return values[middleIndex];
}
};
// Driver code starts
int main() {
vector<vector<int>> mat = {
{1, 3, 5},
{2, 6, 9},
{3, 6, 9}
};
Solution obj;
cout << obj.median(mat) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N × log(M × N)), M is the number of rows and N is the number of columns, because all matrix elements are collected and then sorted together.

Space Complexity: O(M × N), because a separate list of all matrix elements is created where M is the number of rows and N is the number of columns.

Optimal Approach

The key idea is to stop searching for the median position directly and start searching for the median value. Suppose a value x is guessed. Now ask one question: how many elements in the matrix are less than or equal to x?

That question matters because:

  • If too few elements are <= x, then x is too small to be the median.

  • If enough elements are <= x, then the median can be x or some smaller value.

This is the exact reason binary search works here. The matrix is not globally sorted, but every row is sorted. So for any guessed value x, each row can quickly tell how many of its elements are <= x by using binary search inside that row.

That turns the problem into a smooth yes-or-no search:

  • Is the current guessed value still too small?

  • Or has it already reached the median zone?

The median is the smallest value for which more than half of the elements are less than or equal to it.

Algorithm

  • First, find the smallest possible value and the largest possible value in the matrix. This becomes the binary-search range because the median must lie somewhere between them.

  • Compute required = (rows * cols) / 2. This tells how many elements are allowed to stay on the left side of the median. Since indexing is zero-based in thinking here, the actual median must be the first value whose count of <= value becomes greater than required.

  • Keep searching while low < high, because the exact median value is not fixed until the range shrinks to one number.

  • Pick mid = low + (high - low) / 2. This is the current guessed median value.

  • Count how many elements in the full matrix are <= mid. This is done row by row. Since each row is sorted, a binary search like upper_bound can count how many elements are <= mid in that row quickly.

  • If count <= required, move low to mid + 1. This if means the guessed value is still too small, because not enough elements have reached the median position yet.

  • Otherwise, move high to mid. This else means the guessed value is large enough to reach or cross the median position, so the answer can be this value or something smaller.

  • When the loop ends, return low. At that moment, low is the smallest value for which the count of <= value is large enough, and that is exactly the median.

Dry Run

Matrix Median Optimal Dry Run

Matrix Median Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the median value
of the row-wise sorted matrix.
*/
int median(vector<vector<int>>& mat) {
int rows = (int)mat.size();
int cols = (int)mat[0].size();
// These store the smallest and largest possible median values.
int low = mat[0][0];
int high = mat[0][cols - 1];
for (int i = 1; i < rows; i++) {
// The first element of a sorted row can improve the global minimum.
low = min(low, mat[i][0]);
// The last element of a sorted row can improve the global maximum.
high = max(high, mat[i][cols - 1]);
}
// This is how many elements may stay before the median.
int required = (rows * cols) / 2;
while (low < high) {
// This is the current guessed median value.
int mid = low + (high - low) / 2;
int count = 0;
for (int i = 0; i < rows; i++) {
// Count how many values in this row are less than or equal to mid.
count += (int)(upper_bound(mat[i].begin(), mat[i].end(), mid) - mat[i].begin());
}
// Move right because too few elements are still less than or equal to mid.
if (count <= required) {
low = mid + 1;
} else {
// Keep mid in the answer range because it may already be the median.
high = mid;
}
}
return low;
}
};
// Driver code starts
int main() {
vector<vector<int>> mat = {
{1, 3, 5},
{2, 6, 9},
{3, 6, 9}
};
Solution obj;
cout << obj.median(mat) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M + M × log N × log ValueRange), where M is the number of rows, N is the number of columns, and ValueRange is the range between the smallest and largest values in the matrix. The initial O(M) is required to find the minimum and maximum values that define the binary-search range. For every value checked, all M rows are searched using upper_bound, taking O(log N) per row. So, overall time complexity is O(M + M × log N × log ValueRange).

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

The problem statement usually guarantees an odd-sized matrix to make the median straightforward. If it were even, you would typically look for the average of the two middle numbers using a slightly adjusted rank tracking logic.

MathsBinary SearchArraysTwo PointerSorting

Read Similar Blogs

Arrays

Row wise traversal

Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then second row prints as 4 5 6 . Input: mat = [[10, 20], [30, 40], [50, 60]] Output: 10 20 30 40 50...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.5k
Comments0