Problem Statement

Given a row wise sorted matrix of size RxC where R and C are always odd, find the median of the matrix.

Example 1:

Input:
R = 3, C = 3
M = [[1, 3, 5],
     [2, 6, 9],
     [3, 6, 9]]

Output: 5

Explanation:
Sorting matrix elements gives us
{1,2,3,3,5,6,6,9,9}. Hence, 5 is median.

Example 2:

Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output:2

Your Task:  You don't need to read input or print anything. Your task is to complete the function median() which takes the integers R and C along with the 2D matrix as input parameters and returns the median of the matrix.Expected Time Complexity: O(32 * R * log(C))Expected Auxiliary Space: O(1)

**Constraints:**1<= R,C <=1501<= matrix[i][j] <=2000

Problem Link

Median in a row-wise sorted Matrix | Practice | GeeksforGeeks

Reference Video

https://www.youtube.com/watch?v=63fPPOdIr2c&list=PLgUwDviBIf0qYbL4TBaEWgb-ljVdhkM7R&index=3

Code

class Solution{   
public:
    int findNumbersLesserThanOrEqualToMid(vector<int>& row,int target)
    {
        int low = 0;
        int high = row.size()-1;
        
        while(low<=high)
        {
            int mid = (low+high)>>1;
            
            if(row[mid]<=target)
            low = mid + 1;
            
            else
            high = mid-1;
        }
        
        return low;
    }
    
    int median(vector<vector<int>> &matrix, int r, int c){
       
      
       int low = INT_MIN;
       int high = INT_MAX; 
       int m = matrix.size();
       int n = matrix[0].size();
       int target = (m*n)/2; //this many elements should be less than or equal to the median
       
       
       while(low<=high)
       {
           int mid = (low+high)>>1;
           
           int count = 0;
           for(int i=0;i<m;i++)
           {
               count+=findNumbersLesserThanOrEqualToMid(matrix[i],mid);
           }
           
           if(count<=target)
           low = mid+1;
           else
           high = mid-1;
       }
       
       return low;
                
    }
};