Is Median of a Row Wise Sorted Matrix easy or hard?

The problem is typically classified as medium difficulty. The challenge comes from recognizing that the matrix cannot be fully sorted efficiently and that the correct strategy is binary search on the answer combined with row-wise counting.

Median of a Row Wise Sorted Matrix Python/Java solution

The standard implementation performs binary search between the minimum and maximum matrix values. For each midpoint, a binary search (upper bound) is applied to every row to count how many elements are ≤ mid. This approach can be implemented efficiently in Python, Java, C++, and Go using built-in binary search utilities.

How to solve Median of a Row Wise Sorted Matrix in O(n)?

A strict O(n) solution is not possible when rows are only individually sorted. The best practical approach is binary search on the value range combined with row-wise binary searches. This reduces the complexity to O(r log c log valueRange) without scanning every element repeatedly.

What is the best approach for Median of a Row Wise Sorted Matrix?

The most efficient solution uses two binary searches. The outer binary search runs on the value range of the matrix, while the inner binary search counts elements ≤ mid in each row using upper bound. This results in O(r log c log valueRange) time and O(1) space, making it ideal for large matrices.

Is Median of a Row Wise Sorted Matrix asked at Google/Amazon/Meta?

Matrix search and median problems frequently appear in interviews at companies like Amazon, Google, and Microsoft. Variations of this problem test understanding of binary search on answer space and efficient counting in sorted structures.

What data structure is used in Median of a Row Wise Sorted Matrix?

The solution primarily uses arrays (the matrix rows) combined with binary search. Some alternative solutions use a min heap to perform a k-way merge across rows, but the optimal method relies on binary search over the value range.

What is the time complexity of Median of a Row Wise Sorted Matrix?

The optimal algorithm runs in O(r log c log valueRange). For each candidate value in the outer binary search, a binary search is performed in every row to count elements less than or equal to that value. Brute force approaches like flattening and sorting take O((r*c) log(r*c)).

Description Hints 2 Solution Video 14:22

2387. Median of a Row Wise Sorted Matrix

Medium70.9% acceptance1 companyPremium elsewhere, free here

Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix.

You must solve the problem in less than O(m * n) time complexity.

Example 1:

Input: grid = [[1,1,2],[2,3,3],[1,3,4]]
Output: 2
Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.

Example 2:

Input: grid = [[1,1,3,3,4]]
Output: 3
Explanation: The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 500
m and n are both odd.
1 <= grid[i][j] <= 10⁶
grid[i] is sorted in non-decreasing order.

Asked at 1 company

D. E. Shaw

Topics

Hints open one at a time

Hint 1

How can you use the fact that the rows are sorted in non-decreasing order to solve the problem efficiently?

Hint 2

Try to binary search the answer.

14:22

Still stuck?Read the written solution, or watch a walkthrough.

Open solution