2387. Median of a Row Wise Sorted Matrix


Problem Description

The problem presents us with a matrix grid of size m x n (where 'm' represents the number of rows and 'n' represents the number of columns), which contains an odd number of integers. It's stated that the integers in each row of the grid are sorted in non-decreasing order. Our task is to find the median of all the integers in the matrix. But there's a catch: we must find the median in less than O(m * n) time complexity. This condition tells us that we cannot simply sort all the elements of the matrix and pick the middle one, as this would exceed the allowed time complexity.

Intuition

The intuition behind the solution lies in binary search and the understanding of how the median is positioned within a sorted list of numbers. In a sorted list of odd numbers, the median is the middle element. In a matrix form, however, we cannot directly access the middle element since the numbers are spread across rows, but we know that exactly half of the numbers are less than or equal to it, and half are greater than it.

Since each row is sorted, we can make use of this property to apply binary search, but not on the elements directly. Instead, we use binary search on a range of possible values (since we don't have a flat sorted list). We use bisect library in Python which offers a way to determine the position where a number would be inserted to maintain order, which is bisect_right, and bisect_left to return the smallest number such that a given condition is met.

Here's how it works:

  1. Define a search space: The problem hints at the range of elements by suggesting the use of range(10**6 + 1). This means each element can be in the range from 0 to 10**6.

  2. Define the target: Because there's an odd number of elements in the matrix, the median is the (m*n + 1) / 2th smallest element (since Python uses 0-based indexing, we use target = (m * n + 1) >> 1 to get the index).

  3. Counting function: We create a function count(x) that tells us the number of elements in the matrix which are less than or equal to x. This uses bisect_right which counts how many elements in each row are less than or equal to x, and we sum these counts for all rows.

  4. Binary search: We perform a binary search across the possible values of elements and use our count(x) function to determine if a value is too low or too high. We're looking for the smallest number x where count(x) is at least the target number. This x is the median.

In the code:

  • bisect_left(range(10**6 + 1), target, key=count) is the binary search command.
  • It looks through the sorted search space (range(10**6 + 1)) for the value such that at least target numbers in the matrix are less than or equal to it.
  • count function is used as a key to guide the binary search using the count of the elements.

The intuition for why this works is that bisect_left will hone in on the value with enough smaller or equal elements in the rows, thanks to the sorted property of the rows, and the odd number of total elements ensures there’s a definite middle element which is the median.

Solution Approach

The implementation relies heavily on the bisect module from Python's standard library, which is designed for binary searching within a sorted list. By conceptualizing the problem in terms of finding the median via binary search, we avoid having to sort or merge all of the matrix's elements, which enables us to achieve a solution that meets the required time complexity bound.

Here are the key components of the implementation:

  1. Binary Search Space: The range of possible values each element in the matrix can take is from 0 to 10**6. This is established as the binary search space, where bisect_left will search the number that is the median.

  2. Count Function: A helper function count(x) is designed to compute the count of elements that are less than or equal to x. This uses bisect_right, which, when used on each row of the matrix, returns the index at which x should be inserted to keep the row sorted. Summing these indices across all rows gives the total count of elements less than or equal to x.

  3. Target: Since there is an odd total number of elements in the matrix, the median is at the ((m * n) + 1) / 2th smallest element. We right-shift by one bit to find the target index target = (m * n + 1) >> 1 more efficiently (equivalent to integer division by 2).

  4. bisect_left: The binary search is performed by bisect_left(range(10**6 + 1), target, key=count). The range(10**6 + 1) gives us the space in which to look for our median value, target is the number of elements that must be smaller than or equal to our median, and count as the key-function verifies whether the current middle value in our binary search meets the condition of having target number of elements less than or equal to it.

To get a better understanding of how the bisect_left method operates here:

  • bisect_left searches for the insertion point so as to maintain the sorted order. In this case, we are trying to find the smallest number such that there would be target numbers less than or equal to it in the sorted array representation of the matrix.

  • It will go through the whole range(10**6 + 1) one interval at a time, zeroing in on where the median would be if we had one giant sorted list of the elements (but without actually creating this list). At each step of the binary search, bisect_left looks at the count of numbers less than or equal to the middle number it's currently considering and determines whether to search higher or lower.

The combination of these components leads to a solution that efficiently finds the median without directly sorting or flattening the matrix into a list, which would result in a time complexity greater than the allowed O(m * n).

Example Walkthrough

Let's illustrate the solution approach with an example. We are given a 3x3 matrix with non-decreasing rows:

1grid = [
2  [1, 3, 5],
3  [2, 4, 6],
4  [3, 5, 7]
5]

In this grid, m = 3 and n = 3. There are m * n = 9 elements, and we are looking for the median element, which is the (9 + 1) / 2 = 5th smallest element due to the odd number of elements.

  1. Define a search space: The possible values for elements range from 0 to 10**6. In practice, we can use the smallest and largest elements of the matrix as the bounds for binary search. Here, the search space is from 1 to 7.

  2. Define the target: We calculate the target as the median's position. Since there are 9 elements, the median will be the 5th smallest element, so target = 5.

  3. Counting function: We need to count the number of elements less than or equal to some value x. If x = 4, then:

    • In the first row, there are 2 elements (1, 3) less than or equal to 4.
    • In the second row, there are 2 elements (2, 4) less than or equal to 4.
    • In the third row, there are 2 elements (3, 4) less than or equal to 4. The total count for x = 4 is 2 + 2 + 2 = 6.
  4. Binary search: We use bisect_left to perform a binary search within our search space (from 1 to 7), looking for the smallest number x such that the count of numbers less than or equal to x is at least 5 (our target). We start the binary search:

    • Midpoint of 1 and 7 is 4. Counting using our previous counting function, we find 6 elements less than or equal to 4. Therefore, 4 may be too high—we need at least 5 elements, and we found 6—so we will now look for lower numbers.
    • Next we check the interval from 1 to 4, with a midpoint of 2. With x = 2, the total count of elements less than or equal to 2 is 1 + 1 + 1 = 3. This is too low, so we need to search higher.
    • Now we check the interval from 3 to 4, with midpoint 3. With x = 3, the total count of elements less than or equal to 3 is 2 + 1 + 2 = 5. Now we've found exactly 5 elements, which meets our target, and since we're looking for the smallest such number, 3 is our median.

Thus, using the solution approach, we've found that the median of the matrix is 3 without having to flatten and sort the entire matrix. The time complexity of this approach is O(m * log(max-min)), which is significantly less than O(m * n) for large matrices.

Python Solution

1import bisect
2
3class Solution:
4    def matrixMedian(self, grid: List[List[int]]) -> int:
5        # Helper function to count numbers less or equal to x using binary search
6        def count_less_or_equal(x):
7            # Using bisect_right to find the insertion point which gives us 
8            # the count of elements less than or equal to 'x'
9            return sum(bisect.bisect_right(row, x) for row in grid)
10
11        # Get the dimensions of the matrix
12        num_rows, num_cols = len(grid), len(grid[0])
13      
14        # Calculate the target position for median in the sorted array
15        target = (num_rows * num_cols + 1) >> 1  # Equivalent to // 2
16
17        # Function to determine the median by binary searching over the range of values
18        # which could range from 1 to 10**6 considering constraints from the problem
19        def find_median(left, right, target):
20            while left < right:
21                mid = left + (right - left) // 2
22                if count_less_or_equal(mid) < target:
23                    left = mid + 1
24                else:
25                    right = mid
26            return left
27
28        # Initialize the search range between the smallest and largest possible values
29        # based on the problem constraints, then use binary search to find the median
30        return find_median(1, 10**6, target)
31

Java Solution

1class Solution {
2    private int[][] grid; // Initialize a private grid variable to store the input grid.
3
4    // Method to find the median in a row-wise sorted matrix.
5    public int matrixMedian(int[][] grid) {
6        this.grid = grid; // Assign the passed grid to the class's grid variable.
7        int numRows = grid.length; // The number of rows in the grid.
8        int numCols = grid[0].length; // The number of columns in the grid.
9        int target = (numRows * numCols + 1) / 2; // The median's position in the sorted order of elements.
10        int minVal = 0; // Lower bound for the value of median.
11        int maxVal = 1000010; // Upper bound for the value of median.
12
13        // Binary search to find the median value in the matrix.
14        while (minVal < maxVal) {
15            int midVal = (minVal + maxVal) / 2; // Calculate mid value.
16            if (countLessEqual(midVal) >= target) {
17                // If count of elements less than or equal to midVal 
18                // is greater than or equal to target, narrow down the upper half.
19                maxVal = midVal;
20            } else {
21                // If not, narrow down the lower half.
22                minVal = midVal + 1;
23            }
24        }
25        return minVal; // minVal is the median after the end of binary search.
26    }
27
28    // Helper method to count the number of elements less than or equal to x in the matrix.
29    private int countLessEqual(int x) {
30        int count = 0; // Counter for the number of elements less than or equal to x.
31        // Iterate over each row in the grid.
32        for (int[] row : grid) {
33            int left = 0; // Left pointer of the binary search.
34            int right = row.length; // Right pointer of the binary search.
35
36            // Binary search to find the count of elements less than or equal to x in each row.
37            while (left < right) {
38                int mid = (left + right) / 2; // Calculate mid index.
39                if (row[mid] > x) {
40                    // If the current element is greater than x, narrow down the right part.
41                    right = mid;
42                } else {
43                    // Else, narrow down the left part.
44                    left = mid + 1;
45                }
46            }
47            count += left; // Add the numbers less than or equal to x found in the current row to the count.
48        }
49        return count; // Return the total count.
50    }
51}
52

C++ Solution

1#include <vector>
2#include <algorithm> // Include algorithm for using upper_bound
3
4class Solution {
5public:
6    // Function to find the median of the matrix
7    int matrixMedian(vector<vector<int>>& matrix) {
8        int rows = matrix.size();  // Number of rows in the matrix
9        int cols = matrix[0].size();  // Number of columns in the matrix
10
11        // Initializing search space for median
12        int minValue = 0;
13        int maxValue = 1000001; // Assuming 1e6 + 1 as the upper bound of the matrix values
14
15        // Calculate the 'target' as the index after which we have the median
16        int target = (rows * cols + 1) >> 1;  // Use bitwise shift for division by 2
17
18        // Lambda function to count numbers less than or equal to 'x' using 'upper_bound'
19        auto countLessOrEqual = [&](int x) {
20            int count = 0;
21            for (const auto& row : matrix) {
22                // 'upper_bound' returns an iterator to the first element greater than 'x'
23                count += (upper_bound(row.begin(), row.end(), x) - row.begin());
24            }
25            return count;
26        };
27
28        // Binary search to find the median
29        while (minValue < maxValue) {
30            int midValue = (minValue + maxValue) >> 1;  // Finding the mid value for binary search
31
32            // If count of elements less than or equal to 'midValue' is at least 'target'
33            // then median is at 'midValue' or before it.
34            if (countLessOrEqual(midValue) >= target) {
35                maxValue = midValue;  // Continue to search in the left half
36            } else {
37                minValue = midValue + 1;  // Continue to search in the right half
38            }
39        }
40
41        // 'minValue' will hold the median value of the matrix after binary search
42        return minValue;
43    }
44};
45

Typescript Solution

1// Importing array utilities from lodash for operations like 'upperBound'
2import { upperBound } from 'lodash';
3
4// Define a function to find the median of the matrix
5function matrixMedian(matrix: number[][]): number {
6    const rows: number = matrix.length; // Number of rows in the matrix
7    const cols: number = matrix[0].length; // Number of columns in the matrix
8
9    // Initializing the search space for the median
10    let minValue: number = 0;
11    let maxValue: number = 1000001; // Assuming 1e6 + 1 as the upper limit for matrix values
12
13    // Calculate the 'target' index that represents the median position
14    const target: number = ((rows * cols) + 1) >> 1; // Use bitwise shift for division by 2
15
16    // Define a function to count how many numbers in the matrix are less than or equal to 'x'
17    const countLessOrEqual = (x: number): number => {
18        return matrix.reduce((count, row) => {
19            // Find the index of the first element that is greater than 'x'
20            // upperBound from lodash acts similarly to 'upper_bound' in C++
21            count += upperBound(row, x);
22            return count;
23        }, 0);
24    };
25
26    // Perform a binary search to find the median
27    while (minValue < maxValue) {
28        const midValue: number = (minValue + maxValue) >> 1; // Calculate the mid-value
29
30        // If the count of elements less than or equal to 'midValue' is at least 'target'
31        // then the median must be 'midValue' or smaller.
32        if (countLessOrEqual(midValue) >= target) {
33            maxValue = midValue; // Search in the left half
34        } else {
35            minValue = midValue + 1; // Search in the right half
36        }
37    }
38
39    // 'minValue' will hold the median value of the matrix after finishing the binary search
40    return minValue;
41}
42

Time and Space Complexity

The time complexity of the provided code is O(log(MaxElement) * m * n) where MaxElement is the maximum value that an element can take in the grid, m is the number of rows and n is the number of columns in the grid.

The reason for this complexity is that the binary search is performed over a range of [0, 10^6] which requires log(10^6) time. During each step of the binary search, a count of elements less than the current value (x) is performed across all rows, which takes O(m * n) time (m calls to bisect_right, each potentially iterating over up to n elements).

The space complexity of the code is O(1), since no additional space is used that's based on the input size. The only variables in use are for counters and indices, which require a constant amount of space.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫