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.

import java.util.Arrays;

public class MedianInMatrix {
    public static double findMedian(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int totalElements = rows * cols;
        int[] combined = new int[totalElements];
        int index = 0;

        // Combine all elements into a single array
        for (int[] row : matrix) {
            for (int element : row) {
                combined[index++] = element;
            }
        }

        // Sort the combined array
        Arrays.sort(combined);

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

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5},
            {2, 6, 9},
            {3, 6, 9}
        };
        System.out.println("Median: " + findMedian(matrix));
    }
}
            

Output:

Median: 3.0

Method 2: Using Binary Search

This method uses binary search to find the median efficiently.

public class MedianInMatrix {
    public static int countLessEqual(int[][] matrix, int mid) {
        int count = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int 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;
    }

    public static double findMedian(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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, mid) < desired) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low; // The median
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5},
            {2, 6, 9},
            {3, 6, 9}
        };
        System.out.println("Median: " + findMedian(matrix));
    }
}
            

Output:

Median: 3.0

Method 3: Using a Two-Pointer Technique

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

public class MedianInMatrix {
    public static double findMedian(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        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
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5},
            {2, 6, 9},
            {3, 6, 9}
        };
        System.out.println("Median: " + findMedian(matrix));
    }
}
            

Output:

Median: 3.0