Matrix: Find median in a row wise sorted matrix.

Problem Statement:

You are given a row-wise sorted matrix of size r*c. You need to find the median of the matrix.

Example:

Input : 1 3 5
2 6 9
3 6 9
Now put all the values in sorted order. arr [] = 1 2 3 3 5 6 6 9 9
From this array we come to know that the median is 5.

Solution:

This problem can be solved by using number of different approaches. Some of the methods we used in this article are:

1. Brute force approach

2. Modified binary search approach

1. Brute force approach

In this approach we will sort the elements from 2D array to 1D array and get the element at [(1+n*m)/2–1]th index, as the number of elements are always ODD.

In this method the Time Complexity is O(r*c), Space Complexity is O(r*c)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

int median_matrix(int arr[][20], int r, int c) 
{ 
    int tempArr[r*c];
    int desired_index = (1+r*c)/2 -1;
    int index = 0 ;   
    for(int i = 0; i<r; i++)
    {
      for(int j=0; j<c; j++)
      {
         tempArr[index++] = arr[i][j];
      }
    }
    sort(tempArr, tempArr + r*c);
    return tempArr[desired_index];

} 
  
int main() 
{ 
    int r = 3, c = 3; 
    int m[][20]= { {1,3,5}, {2,6,9}, {3,6,9} }; 
    cout << "Median is " << median_matrix(m, r, c) << endl; 
    return 0; 
}

Output:

Median is 5

2. Modified binary search approach

We can take advantage of the following points:

1. Matrix is sorted row wise
2. Matrix will have odd number of elements so the median is (1+N*M)/2 th smallest number
3. As the matrix is sorted we will get the min and max element

1. First we find the min and max element by taking first and last element as the matrix is sorted row wise.

2. We can apply binary search on that range. Then calculate the number of elements smaller or equal to the mid accordingly change the mix or max.

3. If a number to be a median there should be (r*c)/2 number smaller than that number. So for every number get the number less than that number by using upper_bound() in each row of the matrix

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

int median_matrix(int arr[][20], int r, int c) 
{ 

    int min = 999999;
    int max = -1; 

    //get the min and max element
    for (int i=0; i<r; i++) 
    { 
        if (arr[i][0] < min) 
            min = arr[i][0]; 
  
        if (arr[i][c-1] > max) 
            max = arr[i][c-1]; 
    } 
  
    int desired = (r * c + 1) / 2; 
    while (min < max) 
    { 
        int mid = min + (max - min) / 2; 
        int place = 0; 
  
        // Find count of elements smaller than mid 
        for (int i = 0; i < r; ++i) 
            place += upper_bound(arr[i], arr[i]+c, mid) - arr[i]; 
        if (place < desired) 
            min = mid + 1; 
        else
            max = mid; 
    } 
    return min; 
}

int main() 
{ 
    int r = 3, c = 3; 
    int m[][20]= { {1,3,5}, {2,6,9}, {3,6,9} }; 
    cout << "Median is " << median_matrix(m, r, c) << endl; 
    return 0; 
}

Output:

Median is 5