Skip to main content
Talentd

Median of a Row Wise Sorted Matrix - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchMatrix7 min readAsked at: De Shaw
Practice this problem

Problem Statement

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] <= 106
  • grid[i] is sorted in non-decreasing order.

Approach Overview

Problem Overview: You are given a matrix where every row is individually sorted. The task is to compute the median of all elements without flattening the matrix into a single array. Since rows are sorted but columns are not guaranteed to be sorted, traditional median techniques need modification.

Approach 1: Flatten and Sort (O((r*c) log(r*c)) time, O(r*c) space)

The most straightforward method is to copy every element from the matrix into a single array and sort it. After sorting, the median is simply the element at index (r*c)/2. This works because sorting produces the global order of all values. The downside is the extra memory and sorting cost, which becomes expensive for large matrices.

This approach is mainly useful as a baseline or when constraints are small. It ignores the fact that each row is already sorted, so it fails to leverage the structure of the problem.

Approach 2: Min Heap Merge (O(r*c log r) time, O(r) space)

Treat each row as a sorted list and perform a k-way merge using a min heap. Insert the first element from every row into the heap. Repeatedly extract the smallest element and push the next element from the same row. After extracting (r*c)/2 + 1 elements, the last popped value is the median.

This technique is similar to merging k sorted arrays. It reduces memory compared to flattening the matrix and avoids sorting the entire dataset. However, the heap operations still make it slower than the optimal solution when the matrix grows large.

Approach 3: Two Binary Searches (O(r log c log valueRange) time, O(1) space)

The optimal method performs binary search on the value range rather than on indices. The smallest candidate value is the minimum of the first column, and the largest candidate value is the maximum of the last column. For a guessed value mid, count how many elements in the matrix are less than or equal to it.

Each row is sorted, so you can run a binary search (upper bound) in that row to find how many elements are ≤ mid. Summing across rows gives the total count. If the count is less than the desired median position (r*c+1)/2, move the search range higher; otherwise move it lower.

This double binary search efficiently narrows the median without scanning all elements. The outer search runs on the value range, while the inner search uses row ordering. It relies heavily on Binary Search and the structure of a sorted Matrix. The matrix values are accessed directly without extra storage, making the solution space efficient.

Recommended for interviews: Interviewers expect the two binary search solution. Starting with flatten-and-sort shows understanding of the problem, but the optimized method demonstrates deeper knowledge of Array search patterns and how to exploit sorted structure. It scales well even when the matrix contains millions of elements.

Solution

The median is actually the target = \left \lceil \frac{m times n}{2} \right \rceil-th number after sorting.

We perform a binary search on the elements of the matrix x, counting the number of elements in the grid that are greater than x, denoted as cnt. If cnt \ge target, it means the median is on the left side of x (including x); otherwise, it is on the right side.

The time complexity is O(m times log n times log M), where m and n are the number of rows and columns of the grid, respectively, and M is the maximum element in the grid. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Flatten and SortO((r*c) log(r*c))O(r*c)Simple baseline when constraints are small or clarity matters more than efficiency
Min Heap MergeO(r*c log r)O(r)When rows are sorted and you want a streaming merge without storing all elements
Two Binary SearchesO(r log c log valueRange)O(1)Optimal approach that leverages row sorting and avoids flattening the matrix

Video Solution

Leetcode 2387. Median of a Row Wise Sorted Matrix - Binary Search • Code-Yao • 484 views views

Watch 1 more video solutions →

Frequently Asked Questions

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)).

Ready to solve this problem?

Practice Median of a Row Wise Sorted Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays