Matrix Median

Problem Statement

Given a 2D array matrix that is row-wise sorted. The task is to find the median of the given matrix.

Examples

Example 1:

Input: matrix = [
                 [1, 4, 9],
                 [2, 5, 6],
                 [3, 8, 7]
                ]
Output: 5

Explanation: If we find the linear sorted array, the array becomes [1, 2, 3, 4, 5, 6, 7, 8, 9].
So median is the middle element which would be at index 4.
So, median = 5

Example 2:

Input: matrix = [
                 [1, 3, 8],
                 [2, 3, 4],
                 [1, 2, 5]
                ]
Output: 3

Explanation: If we find the linear sorted array, the array becomes [1, 1, 2, 2, 3, 3, 4, 5, 7, 8].
So, median = 3

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The extremely naive approach is to use a linear array or list to store the elements of the given matrix and sort them in increasing manner. The middle element will be the median of matrix.

Approach: 

1. Traverse the rows of the matrix using a for loop.
2. Next, traverse each column of the current row using a nested for loop.
3. Inside the loops, store each element of the current cell to a linear array or list.
4. Finally, return the middle element of that linear array.

Code:

class Solution {
public:
    //Function to find the median of the matrix.
    int findMedian(vector<vector<int>>& matrix) {
        vector<int> lst;
        int n = matrix.size();
        int m = matrix[0].size(); 
        
        /* Traverse the matrix and 
        copy the elements to list*/
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                lst.push_back(matrix[i][j]);
            }
        }
        
        // Sort the list
        sort(lst.begin(), lst.end());
        
        // Return the median element
        return lst[(n * m) / 2];
    }
};

Complexity Analysis:

• Time Complexity: O(m*n) + O(m*n(log m*n)), where n is the number of rows in the matrix, m is the number of columns in each row.
  • At first the matrix is traversed to copy the elements, which takes O(m*n) time complexity.
  • Then, the linear array of size O(m*n) is sorted, which takes O(m*n log(m*n)) time complexity.
• Space Complexity: O(m*n)
  • As we need a temporary list to store the elements.

2️⃣ Binary Search