##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2387.html

# 2387. Median of a Row Wise Sorted Matrix

## Description

Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix.

You must solve the problem in less than O(m * n) time complexity.

Example 1:

Input: grid = [[1,1,2],[2,3,3],[1,3,4]]
Output: 2
Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.


Example 2:

Input: grid = [[1,1,3,3,4]]
Output: 3
Explanation: The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.


Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• m and n are both odd.
• 1 <= grid[i][j] <= 106
• grid[i] is sorted in non-decreasing order.

## Solutions

• class Solution {
private int[][] grid;

public int matrixMedian(int[][] grid) {
this.grid = grid;
int m = grid.length, n = grid.length;
int target = (m * n + 1) >> 1;
int left = 0, right = 1000010;
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid) >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

private int count(int x) {
int cnt = 0;
for (var row : grid) {
int left = 0, right = row.length;
while (left < right) {
int mid = (left + right) >> 1;
if (row[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
cnt += left;
}
return cnt;
}
}

• class Solution {
public:
int matrixMedian(vector<vector<int>>& grid) {
int m = grid.size(), n = grid.size();
int left = 0, right = 1e6 + 1;
int target = (m * n + 1) >> 1;
auto count = [&](int x) {
int cnt = 0;
for (auto& row : grid) {
cnt += (upper_bound(row.begin(), row.end(), x) - row.begin());
}
return cnt;
};
while (left < right) {
int mid = (left + right) >> 1;
if (count(mid) >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};

• class Solution:
def matrixMedian(self, grid: List[List[int]]) -> int:
def count(x):
return sum(bisect_right(row, x) for row in grid)

m, n = len(grid), len(grid)
target = (m * n + 1) >> 1
return bisect_left(range(10**6 + 1), target, key=count)


• func matrixMedian(grid [][]int) int {
m, n := len(grid), len(grid)

count := func(x int) int {
cnt := 0
for _, row := range grid {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] > x {
right = mid
} else {
left = mid + 1
}
}
cnt += left
}
return cnt
}
left, right := 0, 1000010
target := (m*n + 1) >> 1
for left < right {
mid := (left + right) >> 1
if count(mid) >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}