Welcome to Subscribe On Youtube

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[0].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[0].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[0])
            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[0])
    
    	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
    }
    

All Problems

All Solutions