LeetCode 2387: Median of a Row Wise Sorted Matrix

Explanation:

Given a row-wise sorted matrix, we need to find the median of all elements in the matrix.

To solve this problem, we can use binary search to find the median. Since the matrix is row-wise sorted, we can treat all elements as if they are in a single sorted array by considering the matrix as a 1D array.

The idea is to find the mid element of the range [min_element, max_element] in the matrix and then count the number of elements less than or equal to the mid. Based on this count, we can adjust the range for the binary search until we find the median.

Algorithm:

1. Initialize min_element to the smallest element in the matrix and max_element to the largest element in the matrix.
2. Perform binary search on the range [min_element, max_element].
3. For each iteration of binary search, calculate the mid element.
4. Count the number of elements less than or equal to the mid element in the matrix.
5. Adjust the range based on the count to move towards the median.
6. Repeat steps 3-5 until the range converges to the median element.
7. Return the median element.

Time Complexity: O(n * log(m)), where n is the number of rows and m is the number of columns in the matrix.

Space Complexity: O(1)

:

class Solution {
    public double findMedian(int[][] matrix) {
        int minElement = Integer.MAX_VALUE;
        int maxElement = Integer.MIN_VALUE;
        int rows = matrix.length;
        int cols = matrix[0].length;

        for (int row = 0; row < rows; row++) {
            minElement = Math.min(minElement, matrix[row][0]);
            maxElement = Math.max(maxElement, matrix[row][cols - 1]);
        }

        int desiredCount = (rows * cols + 1) / 2;

        while (minElement < maxElement) {
            int mid = minElement + (maxElement - minElement) / 2;
            int count = 0;

            for (int row = 0; row < rows; row++) {
                count += Arrays.binarySearch(matrix[row], mid);
                if (count < 0) {
                    count = -(count + 1);
                }
                count += count;
            }

            if (count < desiredCount) {
                minElement = mid + 1;
            } else {
                maxElement = mid;
            }
        }

        return minElement;
    }
}