This content originally appeared on DEV Community and was authored by Jaspreet singh
Problem Statement
Given a row-wise sorted matrix of size N × M, find the median of the matrix.
The matrix contains an odd number of elements.
Brute Force Intuition
In an interview, you can explain it like this:
Since every row is sorted, one straightforward approach is to collect all elements into a single array, sort them, and return the middle element. This works but ignores the fact that rows are already sorted.
Complexity
- Time Complexity: O(N × M × log(N × M))
- Space Complexity: O(N × M)
Brute Force Code
class Solution {
public int median(int[][] mat) {
List<Integer> list = new ArrayList<>();
for (int[] row : mat) {
for (int num : row) {
list.add(num);
}
}
Collections.sort(list);
return list.get(list.size() / 2);
}
}
Moving Towards the Optimal Approach
Notice that we don't actually need the sorted array.
We only need:
How many numbers are smaller than or equal to X?
If we can answer this efficiently, we can binary search the median value.
Pattern Recognition
Whenever you see:
- Sorted Rows
- Find kth smallest / median
- Value range known
Think:
Binary Search on Answer
Key Observation
Suppose:
mid = 10
Count:
How many elements ≤ 10 ?
If that count is:
Too small
Median lies on the right.
If count is:
Large enough
Median lies on the left.
Why Upper Bound?
Each row is sorted.
For every row we can find:
Count of elements ≤ mid
using Binary Search.
This takes:
O(log M)
per row.
Optimal Java Solution
class Solution {
public int median(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
int low = 1;
int high = 2000;
int required = (n * m) / 2;
while (low <= high) {
int mid = low + (high - low) / 2;
int count = 0;
for (int[] row : mat) {
count += upperBound(row, mid);
}
if (count <= required) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
private int upperBound(int[] row, int target) {
int low = 0;
int high = row.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (row[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
}
Dry Run
Input
1 3 5
2 6 9
3 6 9
Total Elements:
9
Median Position:
9 / 2 = 4
Need the 5th smallest element.
Iteration 1
mid = 5
Count elements ≤ 5:
Row1 → 3
Row2 → 1
Row3 → 1
Total = 5
Since:
5 > 4
Move Left.
Iteration 2
mid = 3
Count elements ≤ 3:
Row1 → 2
Row2 → 1
Row3 → 1
Total = 4
Since:
4 <= 4
Move Right.
Result
Median = 5
Why Binary Search Works?
We are not searching indices.
We are searching values.
For every value:
Count(elements ≤ value)
This count grows monotonically.
Hence Binary Search becomes possible.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(log(MaxValue) × N × log M) |
| Space Complexity | O(1) |
Where:
-
log(MaxValue)→ Binary Search on answer. -
log(M)→ Upper Bound in each row.
Interview One-Liner
Binary search the value range and count how many elements are ≤ mid using upper bound on every sorted row.
Pattern Learned
Sorted Structure
+
Need kth Smallest / Median
+
Monotonic Count
=> Binary Search on Answer
Similar Problems
- Median in Matrix
- Kth Smallest Element in Matrix
- Aggressive Cows
- Koko Eating Bananas
- Nth Root of Number
- Capacity to Ship Packages
Memory Trick
Think:
Guess a Number (mid)
Count:
How many elements ≤ mid ?
Count Too Small
→ Move Right
Count Large Enough
→ Move Left
Mental Model
Binary Search on Index
→ Search Position
Binary Search on Answer
→ Search Value
Whenever you hear:
"Median in Sorted Matrix"
your brain should immediately think:
Count Elements ≤ Mid + Binary Search on Answer
This content originally appeared on DEV Community and was authored by Jaspreet singh
Jaspreet singh | Sciencx (2026-06-20T17:43:48+00:00) Median in a Row Wise Sorted Matrix | Binary Search on Answer. Retrieved from https://www.scien.cx/2026/06/20/median-in-a-row-wise-sorted-matrix-binary-search-on-answer/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.