# 2387. Median of a Row Wise Sorted Matrix

• Time: $O(\log(10^6) \cdot m\log n) = O(m\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: int matrixMedian(vector>& grid) { const int noGreaterThanMedianCount = grid.size() * grid[0].size() / 2 + 1; int l = 1; int r = 1e6; while (l < r) { const int m = (l + r) / 2; if (numsNoGreaterThan(grid, m) >= noGreaterThanMedianCount) r = m; else l = m + 1; } return l; } private: int numsNoGreaterThan(const vector>& grid, int m) { int count = 0; for (const vector& row : grid) count += upper_bound(row.begin(), row.end(), m) - row.begin(); return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int matrixMedian(int[][] grid) { final int noGreaterThanMedianCount = grid.length * grid[0].length / 2 + 1; int l = 1; int r = (int) 1e6; while (l < r) { final int m = (l + r) / 2; if (numsNoGreaterThan(grid, m) >= noGreaterThanMedianCount) r = m; else l = m + 1; } return l; } private int numsNoGreaterThan(int[][] grid, int m) { int count = 0; for (int[] row : grid) count += firstGreater(row, m); return count; } private int firstGreater(int[] row, int target) { int l = 0; int r = row.length; while (l < r) { final int m = (l + r) / 2; if (row[m] > target) r = m; else l = m + 1; } return l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def matrixMedian(self, grid: List[List[int]]) -> int: noGreaterThanMedianCount = len(grid) * len(grid[0]) // 2 + 1 l = 1 r = int(1e6) while l < r: m = (l + r) // 2 if sum(bisect_right(row, m) for row in grid) >= \ noGreaterThanMedianCount: r = m else: l = m + 1 return l