Find Median in a Row-wise Sorted Matrix

Given an M x N matrix where each row is sorted in ascending order, find the median of the matrix. The matrix has an odd number of elements, ensuring that there is always a unique median.

Input/Output Examples

plaintext
Example 1:
Input:
matrix = [
    [1, 3, 5],
    [2, 6, 9],
    [3, 6, 9]]

Output: 5
Explanation: The sorted elements are [1, 2, 3, 3, 5, 6, 6, 9, 9], and 5 is the median.

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

Output: 5
Explanation: The sorted elements are [1, 2, 3, 4, 5, 6, 7, 8, 9], and 5 is the median.

Approach to Find Median in a Row-wise Sorted Matrix

  1. Binary Search on Possible Value Range:
    • The matrix is row-wise sorted, so the minimum value is at matrix[0][0], and the maximum value is at matrix[M-1][N-1]. Use binary search within this value range to find the median.
  2. Count Elements Less Than or Equal to Mid Value:
    • For a given mid value, count how many elements in the matrix are less than or equal to it. This can be done efficiently for each row using binary search due to the sorted nature of each row.
  3. Adjust the Search Range:
    • If the count of elements less than or equal to mid is less than or equal to half the total elements, move the range right to increase the mid.
    • If the count is greater, move the range left to decrease the mid.
  4. Find the Median:
    • The median is the smallest value for which the count of elements less than or equal to it is greater than half the total elements.

C++ Program to Find Median in a Row-wise Sorted Matrix

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to count elements less than or equal to mid in each row
int countLessOrEqual(const vector<int>& row, int mid) {
    return upper_bound(row.begin(), row.end(), mid) - row.begin();
}

// Function to find the median in a row-wise sorted matrix
int findMedian(const vector<vector<int>>& matrix) {
    int low = matrix[0][0];
    int high = matrix[matrix.size() - 1][matrix[0].size() - 1];
    int desiredCount = (matrix.size() * matrix[0].size()) / 2;

    while (low < high) {
        int mid = low + (high - low) / 2;
        int count = 0;

        for (const auto& row : matrix) {
            count += countLessOrEqual(row, mid);
        }

        if (count <= desiredCount) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };

    int result = findMedian(matrix);
    cout << "Median: " << result << endl;
    return 0;
}

Java Program to Find Median in a Row-wise Sorted Matrix

java
import java.util.Arrays;

public class MedianInSortedMatrix {

    // Function to count elements less than or equal to mid in each row
    public static int countLessOrEqual(int[] row, int mid) {
        int pos = Arrays.binarySearch(row, mid);
        if (pos < 0) pos = -pos - 1;
        else while (pos < row.length && row[pos] == mid) pos++;
        return pos;
    }

    // Function to find the median in a row-wise sorted matrix
    public static int findMedian(int[][] matrix) {
        int low = matrix[0][0];
        int high = matrix[matrix.length - 1][matrix[0].length - 1];
        int desiredCount = (matrix.length * matrix[0].length) / 2;

        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = 0;

            for (int[] row : matrix) {
                count += countLessOrEqual(row, mid);
            }

            if (count <= desiredCount) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5},
            {2, 6, 9},
            {3, 6, 9}
        };

        int result = findMedian(matrix);
        System.out.println("Median: " + result);
    }
}

Python Program to Find Median in a Row-wise Sorted Matrix

python
import bisect

# Function to count elements less than or equal to mid in each row
def count_less_equal(row, mid):
    return bisect.bisect_right(row, mid)

# Function to find the median in a row-wise sorted matrix
def find_median(matrix):
    low = matrix[0][0]
    high = matrix[-1][-1]
    desired_count = (len(matrix) * len(matrix[0])) // 2

    while low < high:
        mid = (low + high) // 2
        count = 0

        for row in matrix:
            count += count_less_equal(row, mid)

        if count <= desired_count:
            low = mid + 1
        else:
            high = mid

    return low

# Example usage
if __name__ == "__main__":
    matrix = [
        [1, 3, 5],
        [2, 6, 9],
        [3, 6, 9]
    ]
    result = find_median(matrix)
    print("Median:", result)
  • Time Complexity: O(M * log N * log(max - min)), where M is the number of rows and N is the number of columns. The binary search runs in log(max - min) and each count operation takes O(log N).
  • Space Complexity: O(1), since we are using a constant amount of extra space, regardless of the matrix size.

DSA

7388

832

Related Articles