LeetCode Problem 2387

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Matrix

Solution

LeetCode 2387. Median of a Row Wise Sorted Matrix

Problem Understanding

We are given an m × n matrix grid where every row is already sorted in non-decreasing order. The total number of elements in the matrix is guaranteed to be odd because both m and n are odd.

The task is to find the median of all values contained in the matrix.

If we conceptually flatten the matrix into a single list and sort all elements, the median is the middle element. Since the total number of elements is odd, there is exactly one middle position.

For example:

[[1,1,2],
 [2,3,3],
 [1,3,4]]

contains:

1,1,2,2,3,3,1,3,4

After sorting:

1,1,1,2,2,3,3,3,4

The middle element is 2, so the answer is 2.

The important challenge is the time complexity requirement. A straightforward solution would collect every value, sort them, and return the middle element. However, that requires at least O(m * n log(m * n)) time, which violates the requirement that the solution be faster than O(m * n).

The constraints are:

• 1 ≤ m, n ≤ 500
• Each row is sorted.
• Values range from 1 to 10^6.
• Both dimensions are odd.

The largest possible matrix contains:

500 × 500 = 250,000

elements.

Because rows are already sorted, we should exploit that structure instead of sorting the entire matrix again.

Some important edge cases include:

• A matrix consisting of a single element.
• A single row matrix.
• A single column matrix.
• Many duplicate values.
• Cases where the median value appears multiple times.
• Cases where the minimum and maximum values differ greatly.

The problem guarantees that every row is sorted, which is the key property that enables an efficient solution.

Problem Understanding

The problem gives us an m x n matrix where every individual row is sorted in non-decreasing order. The total number of elements in the matrix is guaranteed to be odd because both m and n are odd. Our task is to return the median element of all numbers in the matrix.

The important detail is that the matrix is not globally sorted. Only each row is sorted independently. That means if we flatten the matrix row by row, the resulting array is not necessarily sorted. For example:

[
  [1, 3, 5],
  [2, 6, 9],
  [3, 6, 9]
]

The rows are sorted, but the full matrix ordering is not.

The median of an odd-length collection is the middle element after sorting all elements. Since there are m * n elements, the median is the element at index:

(m * n) // 2

in zero-based indexing after sorting.

The constraints are extremely important here:

• m, n <= 500
• Maximum number of elements is 250000
• Values range up to 10^6
• We must solve the problem in less than O(m * n) time

A naive solution that flattens and sorts all values would take:

O(m * n * log(m * n))

which violates the intended constraint.

The key observation is that although the matrix is not globally sorted, every row individually is sorted. This allows us to efficiently count how many values are less than or equal to a target number using binary search.

Several edge cases are important:

• A matrix with only one row
• A matrix where all values are identical
• Many duplicate values around the median
• Very small matrices like 1 x 1
• Cases where the median appears multiple times

The problem guarantees:

• The matrix always contains an odd number of elements
• Every row is already sorted
• There is always exactly one median value to return

Approaches

Brute Force Approach

The most direct solution is to flatten the matrix into a single array, sort the array, and return the middle element.

Since there are m * n elements, sorting requires:

O((m*n) log(m*n))

time.

This approach is correct because sorting all elements explicitly gives their exact order, making it trivial to pick the median.

However, the problem specifically asks for a solution faster than O(m*n), so sorting all elements is not acceptable.

Key Insight

Notice that each row is already sorted.

Instead of searching for the median's position among indices, we can search for the median's value.

Suppose we guess a value x.

We can efficiently count how many matrix elements are less than or equal to x.

Because every row is sorted, this count can be obtained with binary search inside each row.

This gives us a monotonic property:

• If too few elements are ≤ x, then the median must be larger.
• If enough elements are ≤ x, then the median is at most x.

This monotonic behavior allows us to perform binary search on the value range rather than on matrix positions.

Since values are between 1 and 10^6, value-space binary search is extremely efficient. The most straightforward solution is to flatten the matrix into a single array, sort it, and return the middle element.

We iterate through every row and append all elements into one list. After sorting the list, the median is simply the middle element.

This works because sorting produces the exact global ordering of all elements in the matrix.

However, this approach is too slow for the intended constraints. If there are k = m * n elements, sorting requires:

O(k log k)

With up to 250000 elements, this becomes significantly more expensive than necessary.

Optimal Approach

The important insight is that we do not actually need to fully sort the matrix. We only need to determine which value is the median.

Since each row is sorted, we can efficiently count how many elements are less than or equal to a chosen value x.

For any candidate number x:

• If fewer than half the elements are <= x, then the median must be larger
• Otherwise, the median is less than or equal to x

This creates a monotonic condition that allows binary search on the value range rather than on indices.

We binary search between the minimum possible matrix value and the maximum possible matrix value. For each midpoint:

• Use binary search inside every row to count elements <= mid
• Compare the count against the desired median position
• Narrow the search space accordingly

The rows being sorted is what makes this efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m_n) log(m_n))	O(m*n)	Flatten and sort all elements
Optimal	O(m log n log V)	O(1)	Binary search on value range, where V = maxValue - minValue

Algorithm Walkthrough

1. Compute the total number of elements:

total = m × n

2. Determine the median position.

Since indexing is zero-based, the median is the element that has exactly:

total // 2

elements before it. 3. Find the smallest and largest possible values in the matrix.

Because rows are sorted:

• The smallest value is among the first elements of rows.
• The largest value is among the last elements of rows.

These become the search boundaries. 4. Perform binary search on the value range.

Let:

low = minimum value
high = maximum value

5. For each candidate value mid, count how many matrix elements are less than or equal to mid.

Since each row is sorted, use binary search (bisect_right) to find the insertion position of mid in that row.

The insertion position equals the number of elements in that row that are ≤ mid. 6. Sum these counts across all rows. 7. Compare the count against the desired median position.

• If the count is less than or equal to total // 2, then not enough elements are small enough, so the median must be larger.
• Otherwise, the median is at most mid.

8. Continue shrinking the search interval until low == high.
9. Return that value.

Why it works

For any value x, define:

count(x) = number of matrix elements ≤ x

This function is monotonic non-decreasing.

The median is precisely the smallest value whose count exceeds half of the elements. Binary search finds that boundary value. Because every count is computed exactly using row-wise binary searches, the returned value is the true median. | Brute Force | O(m * n * log(m * n)) | O(m * n) | Flatten and sort all elements | | Optimal | O(m * log(maxValue) * log n) | O(1) | Binary search on answer space |

Algorithm Walkthrough

Optimal Algorithm

1. Determine the search range for the median value.

Since rows are sorted, the smallest possible value must be among the first elements of rows, and the largest possible value must be among the last elements of rows.

We initialize:

low = minimum first element across rows
high = maximum last element across rows

2. Compute the target median position.

The matrix contains:

total = m * n

Since the number of elements is odd, the median position is:

target = total // 2

3. Perform binary search on the value range.

We repeatedly compute:

mid = (low + high) // 2

We now ask:

How many elements in the matrix are <= mid?

4. Count elements less than or equal to mid.

Because every row is sorted, we can use binary search inside each row.

In Python, bisect_right(row, mid) returns the number of elements <= mid.

Summing this across all rows gives the total count. 5. Decide which half to keep.

If the count is less than or equal to the target index, then the median must be larger than mid.

Otherwise, the median is less than or equal to mid.

So:

if count <= target:
    low = mid + 1
else:
    high = mid

6. Continue until the search converges.

Eventually:

low == high

This value is the smallest number such that more than half the elements are less than or equal to it, which is exactly the median.

Why it works

The algorithm relies on a monotonic property.

As the candidate value increases, the number of matrix elements less than or equal to that value can only increase. This means we can binary search over the value space.

The median is the smallest value for which the count of elements <= value exceeds half the matrix size. Binary search correctly identifies this boundary.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def matrixMedian(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        low = min(row[0] for row in grid)
        high = max(row[-1] for row in grid)

        target = (rows * cols) // 2

        target = (rows * cols) // 2

        low = min(row[0] for row in grid)
        high = max(row[-1] for row in grid)

        while low < high:
            mid = (low + high) // 2

            count = 0

            for row in grid:
                count += bisect_right(row, mid)

            if count <= target:
                low = mid + 1
            else:
                high = mid

        return low

Implementation Explanation

The first step computes the global minimum and maximum values. Because every row is sorted, the smallest value in a row is its first element and the largest value is its last element.

The variable target stores the median index:

(rows * cols) // 2

The binary search operates over the value range rather than matrix indices.

For every candidate value mid, we count how many values are less than or equal to it. The bisect_right function returns exactly this quantity for a sorted row.

If that count is not large enough to reach the median position, we move the search interval upward. Otherwise, we keep searching the lower half because the median could still be smaller.

When the interval collapses to a single value, that value is the median. The implementation follows the algorithm directly.

First, we compute the matrix dimensions and determine the target median index. Since the total number of elements is odd, the median is always the element at position (rows * cols) // 2.

Next, we initialize the binary search range. Because every row is sorted:

• The smallest matrix value must be one of the first elements
• The largest matrix value must be one of the last elements

Inside the binary search loop, we compute the midpoint and count how many elements are less than or equal to it.

The key optimization is bisect_right. Since each row is sorted, binary search gives the insertion position after all occurrences of mid, which is exactly the number of elements <= mid.

After summing counts across all rows:

• If too few elements are <= mid, the median must be larger
• Otherwise, the median is at most mid

The loop converges to the exact median value.

Go Solution

package main

import "sort"

func matrixMedian(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	target := (rows * cols) / 2

	low := grid[0][0]
	high := grid[0][cols-1]

	for _, row := range grid {
		if row[0] < low {
			low = row[0]
		}

		if row[cols-1] > high {
			high = row[cols-1]
		}
	}

	target := (rows * cols) / 2

	for low < high {
		mid := low + (high-low)/2

		count := 0

		for _, row := range grid {
			count += sort.SearchInts(row, mid+1)
		}

		if count <= target {
			low = mid + 1
		} else {
			high = mid
		}
	}

	return low
}

Go-Specific Notes

Go does not provide a direct equivalent of Python's bisect_right, but sort.SearchInts(row, mid+1) produces the same result. It returns the first position where mid + 1 could be inserted, which is exactly the count of elements less than or equal to mid.

The binary search midpoint is computed as: The Go implementation mirrors the Python solution closely.

The main difference is the use of sort.SearchInts instead of bisect_right.

sort.SearchInts(row, mid+1)

returns the insertion position of mid + 1, which is equivalent to counting elements <= mid.

The binary search midpoint is computed carefully:

mid := low + (high-low)/2

which avoids potential integer overflow, although overflow is not a practical concern under the given constraints. This avoids potential integer overflow in languages where integers have fixed size.

Go slices are naturally used for rows, and no additional memory allocation is required beyond a few integer variables.

Worked Examples

Example 1

grid =
[[1,1,2],
 [2,3,3],
 [1,3,4]]
Input:

grid = [ [1,1,2], [2,3,3], [1,3,4] ]

Total elements:

9

Target:
Median position:

9 // 2 = 4

Initial range:
Search range:

low = 1 high = 4

| Iteration | low | high | mid | Count ≤ mid | Action |
| --- | --- | --- | --- | --- | --- |
| 1 | 1 | 4 | 2 | 5 | high = 2 |
| 2 | 1 | 2 | 1 | 3 | low = 2 |
### Iteration 1

mid = (1 + 4) // 2 = 2

Count elements `<= 2`.

| Row | Elements <= 2 | Count |
| --- | --- | --- |
| [1,1,2] | 1,1,2 | 3 |
| [2,3,3] | 2 | 1 |
| [1,3,4] | 1 | 1 |

Total count:

5

Since:

5 > 4

move left:

high = 2

### Iteration 2

mid = (1 + 2) // 2 = 1

Count elements `<= 1`.

| Row | Elements <= 1 | Count |
| --- | --- | --- |
| [1,1,2] | 1,1 | 2 |
| [2,3,3] | none | 0 |
| [1,3,4] | 1 | 1 |

Total count:

3

Since:

3 <= 4

move right:

low = 2

Now:

low = high = 2

Return:
low == high == 2

Answer:

2

Example 2

Input:

grid = [[1,1,3,3,4]]

Total elements:

5

Target: Median position:

2

Initial range: Search range:

low = 1
high = 4

Iteration	low	high	mid	Count ≤ mid	Action
1	1	4	2	2	low = 3
2	3	4	3	4	high = 3

Iteration 1

mid = 2

Elements <= 2:

1,1

Count:

2

Since:

2 <= target

move right:

low = 3

Iteration 2

mid = 3

Elements <= 3:

1,1,3,3

Count:

4

Since:

4 > target

move left:

high = 3

Now:

low = high = 3

Return: low == high == 3

Answer:

3

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(m log n log V) | Binary search over values, each step performs binary search in every row |
| Space | O(1) | Only a few variables are used |

The value-space binary search requires `O(log V)` iterations, where `V` is the range of possible values. For each iteration, we process all `m` rows and perform a binary search of cost `O(log n)` within each row. Therefore the total running time is:

O(m log n log V)

With values bounded by `10^6`, `log V` is approximately 20, making the algorithm very efficient for the maximum matrix size.
| Time | `O(m * log(maxValue) * log n)` | Binary search on value range, binary search inside each row |
| Space | `O(1)` | Only constant extra variables are used |

The outer binary search runs across the numeric value range. Since values are bounded by `10^6`, the number of iterations is roughly:

log2(10^6) ≈ 20

For each iteration, we process all `m` rows. Inside each row, we perform binary search in `O(log n)` time.

Therefore:

O(m * log(maxValue) * log n)

The algorithm uses constant extra space because no auxiliary arrays or heaps are allocated.

## Test Cases

```python
from typing import List

s = Solution()

assert s.matrixMedian([[1,1,2],[2,3,3],[1,3,4]]) == 2  # example 1

assert s.matrixMedian([[1,1,3,3,4]]) == 3  # example 2

assert s.matrixMedian([[5]]) == 5  # single element

assert s.matrixMedian([[1],[3],[5]]) == 3  # single column

assert s.matrixMedian([[1,2,3]]) == 2  # single row

assert s.matrixMedian([[1,1,1],[1,1,1],[1,1,1]]) == 1  # all equal

assert s.matrixMedian([[1,2,2],[2,2,3],[3,3,4]]) == 2  # many duplicates

assert s.matrixMedian([[1,2,3],[4,5,6],[7,8,9]]) == 5  # distinct values

assert s.matrixMedian([[1,1,1],[1,2,2],[2,2,2]]) == 2  # median repeated

assert s.matrixMedian([[1,1000000,1000000]]) == 1000000  # large value range

assert s.matrixMedian([[1,2,3],[3,3,3],[3,4,5]]) == 3  # median appears frequently

Test Summary

Test	Why
[[1,1,2],[2,3,3],[1,3,4]]	Official example
[[1,1,3,3,4]]	Official single-row example
[[5]]	Smallest possible matrix
[[1],[3],[5]]	Single-column matrix
[[1,2,3]]	Single-row matrix
All values equal	Verifies duplicate handling
Many duplicates	Tests counting correctness
Distinct sorted values	Standard median case
Median repeated many times	Boundary behavior around median
Large value range	Tests value-space binary search
Frequent median occurrences	Confirms correct lower-bound search

Edge Cases

Single Element Matrix

A matrix containing only one value is the smallest valid input. A naive implementation might assume multiple rows or columns exist and accidentally access invalid indices. The algorithm handles this naturally because low and high are initialized to the same value, causing the binary search loop to terminate immediately and return that element.

Large Number of Duplicate Values

Many matrices contain repeated values, including cases where the median appears several times. An incorrect implementation might search for the first occurrence or a specific index rather than the median value itself. Using bisect_right counts every occurrence of a value correctly, ensuring duplicates are handled exactly.

Single Row or Single Column

When m = 1 or n = 1, the matrix effectively becomes a sorted array. Some matrix-specific algorithms can fail because they assume multiple rows and columns. This solution still works because every count operation is performed row by row, and binary search within a row remains valid regardless of how many rows exist.

Extremely Large Value Range

Values may range from 1 to 10^6. Searching directly among all possible values could appear expensive, but binary search reduces the number of iterations to roughly log2(10^6) ≈ 20. Therefore the algorithm remains efficient even when the minimum and maximum values are very far apart.

Median Appearing Multiple Times

The median value may occupy several consecutive positions in the sorted order. The algorithm searches for the smallest value whose cumulative count exceeds half of the elements. This lower-bound behavior guarantees that the correct median value is returned even when many equal values surround the median position. from bisect import bisect_right

class Solution: def matrixMedian(self, grid: List[List[int]]) -> int: rows = len(grid) cols = len(grid[0])

    target = (rows * cols) // 2

    low = min(row[0] for row in grid)
    high = max(row[-1] for row in grid)

    while low < high:
        mid = (low + high) // 2

        count = 0

        for row in grid:
            count += bisect_right(row, mid)

        if count <= target:
            low = mid + 1
        else:
            high = mid

    return low

sol = Solution()

assert sol.matrixMedian([[1,1,2],[2,3,3],[1,3,4]]) == 2

Standard multi-row example

assert sol.matrixMedian([[1,1,3,3,4]]) == 3

Single row matrix

assert sol.matrixMedian([[5]]) == 5

Smallest possible matrix

assert sol.matrixMedian([[1,2,3],[4,5,6],[7,8,9]]) == 5

Strictly increasing values

assert sol.matrixMedian([[1,1,1],[1,1,1],[1,1,1]]) == 1

All values identical

assert sol.matrixMedian([[1,2,2],[2,2,3],[3,3,4]]) == 2

Many duplicates around median

assert sol.matrixMedian([[1,10,20],[2,12,30],[3,13,40]]) == 12

Median from middle row

assert sol.matrixMedian([[1],[2],[3]]) == 2

Single column matrix

assert sol.matrixMedian([[1000000]]) == 1000000

Maximum value boundary

assert sol.matrixMedian([[1,1,1],[1,2,2],[2,2,2]]) == 2

Median appears multiple times

| Test | Why |
| --- | --- |
| `[[1,1,2],[2,3,3],[1,3,4]]` | Standard mixed matrix |
| `[[1,1,3,3,4]]` | Single row handling |
| `[[5]]` | Smallest valid input |
| `[[1,2,3],[4,5,6],[7,8,9]]` | Fully increasing values |
| `[[1,1,1],[1,1,1],[1,1,1]]` | All duplicates |
| `[[1,2,2],[2,2,3],[3,3,4]]` | Duplicate-heavy median |
| `[[1,10,20],[2,12,30],[3,13,40]]` | Median not near extremes |
| `[[1],[2],[3]]` | Single column matrix |
| `[[1000000]]` | Maximum value boundary |
| `[[1,1,1],[1,2,2],[2,2,2]]` | Median repeated many times |

## Edge Cases

One important edge case is a matrix with only one element. In this scenario, that single value is trivially the median. Some implementations accidentally assume multiple rows or columns exist, which can cause index errors. This implementation handles the case naturally because the binary search range becomes a single value immediately.

Another important case is when all matrix values are identical. For example:

[ [7,7,7], [7,7,7], [7,7,7] ]

A poorly implemented binary search may get stuck in an infinite loop if the boundaries are not updated correctly. In this solution, the search converges safely because the interval shrinks every iteration.

Duplicate-heavy matrices are another common source of bugs. Consider:

[ [1,2,2], [2,2,3], [3,3,4] ]

The median value appears multiple times. Using `bisect_left` instead of `bisect_right` would produce incorrect counts because we specifically need the number of elements `<= mid`. The implementation correctly uses upper-bound style binary search.

A single-column matrix is also important:

[ [1], [2], [3] ]

Even though each row has length one, the algorithm still works because binary search on a one-element row remains valid. The implementation does not rely on rows having multiple elements.

Finally, matrices where the median lies near the numeric extremes test the correctness of the value-space binary search. Since the algorithm searches over actual values rather than indices, it correctly handles values anywhere within the allowed range up to `10^6`.