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.

Learn more about Binary Search patterns.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.