Find Median in a Row-Wise Sorted Matrix

Understanding the Problem

The goal is to find the median of a row-wise sorted matrix.

Method 1: Using a Combined Array

This method combines all elements into a single array and then finds the median.

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

double findMedian(int matrix[][100], int rows, int cols) {
    int totalElements = rows * cols;
    int combined[totalElements];
    int index = 0;

    // Combine all elements into a single array
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            combined[index++] = matrix[i][j];
        }
    }

    // Sort the combined array
    sort(combined, combined + totalElements);

    // Find the median
    if (totalElements % 2 == 0) {
        return (combined[totalElements / 2 - 1] + combined[totalElements / 2]) / 2.0;
    } else {
        return combined[totalElements / 2];
    }
}

int main() {
    int matrix[100][100] = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };
    int rows = 3, cols = 3;
    cout << "Median: " << findMedian(matrix, rows, cols) << endl;
    return 0;
}
            

Output:

Median: 3.0

Method 2: Using Binary Search

This method uses binary search to find the median efficiently.

#include <iostream>
using namespace std;

int countLessEqual(int matrix[][100], int rows, int cols, int mid) {
    int count = 0, row = rows - 1, col = 0;

    while (row >= 0 && col < cols) {
        if (matrix[row][col] <= mid) {
            count += (row + 1); // All elements in this row are <= mid
            col++;
        } else {
            row--;
        }
    }
    return count;
}

double findMedian(int matrix[][100], int rows, int cols) {
    int low = 0, high = 100000; // Assuming the range of elements
    int desired = (rows * cols + 1) / 2; // Median position

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(matrix, rows, cols, mid) < desired) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low; // The median
}

int main() {
    int matrix[100][100] = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };
    int rows = 3, cols = 3;
    cout << "Median: " << findMedian(matrix, rows, cols) << endl;
    return 0;
}
            

Output:

Median: 3.0

Method 3: Using a Two-Pointer Technique

This method uses a two-pointer technique to find the median.

#include <iostream>
using namespace std;

double findMedian(int matrix[][100], int rows, int cols) {
    int totalElements = rows * cols;
    int medianPos = (totalElements - 1) / 2;
    int count = 0, current = 0;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            current = matrix[i][j];
            if (count == medianPos) {
                return current; // Found the median
            }
            count++;
        }
    }
    return -1; // Should not reach here
}

int main() {
    int matrix[100][100] = {
        {1, 3, 5},
        {2, 6, 9},
        {3, 6, 9}
    };
    int rows = 3, cols = 3;
    cout << "Median: " << findMedian(matrix, rows, cols) << endl;
    return 0;
}
            

Output:

Median: 3.0