Median of a Row Wise Sorted Matrix - Practice Coding Problems

Median of a Row Wise Sorted Matrix - Problem

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.

Note: The median is the middle element when all elements are sorted in ascending order. Since the matrix contains an odd number of elements, there will always be exactly one median element.

Input & Output

Example 1 — Basic 3x3 Matrix

$ Input: grid = [[1,3,5],[2,6,9],[3,6,9]]

› Output: 5

💡 Note: Sorted elements: [1,2,3,3,5,6,6,9,9]. The median (middle element at index 4) is 5.

Example 2 — Different Values

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 5

💡 Note: All elements in order: [1,2,3,4,5,6,7,8,9]. The median is the middle element 5 at index 4.

Example 3 — Repeated Values

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

› Output: 3

💡 Note: Sorted: [1,1,2,2,3,3,3,3,3]. The median at position 4 (0-indexed) is 3.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 500
m * n is odd
1 ≤ grid[i][j] ≤ 10⁶
grid[i] is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x3 matrix with 9 elements, each row sorted

Conceptual Sort

If we sorted all elements: [1,2,3,3,5,6,6,9,9]

Find Median

Middle element at index 4 is our answer: 5

Key Takeaway

🎯 Key Insight: Binary search on the value range rather than positions, using the sorted property to count efficiently

Asked in

G Google 25 M Microsoft 20 a Amazon 18 f Facebook 15

The key insight is to binary search on the answer space rather than positions. Since we need better than O(m*n), we avoid collecting all elements. The optimal approach uses binary search on value range [min, max] and counts elements ≤ each candidate. Time: O(m * log(max-min) * log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(m * log(max-min) * log n)	O(1)	Binary search on possible median values, count elements ≤ each candidate
Collect All Elements and Sort	O(mnlog(m*n))	O(m*n)	Flatten matrix to array, sort, and find middle element

Binary Search on Answer Space — Algorithm Steps

Find min and max values in matrix
Binary search on value range [min, max]
For each mid value, count elements ≤ mid across all rows
Adjust search based on count vs required median position

Visualization

Tap to expand

Step-by-Step Walkthrough

Value Range

Find min=1, max=9 from matrix corners

Binary Search

Try middle value (5) and count elements ≤ 5

Count & Decide

5 elements ≤ 5, which is median position, so answer is 5

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int countLessEqual(int** grid, int gridSize, int* gridColSize, int target) {
    int count = 0;
    for (int i = 0; i < gridSize; i++) {
        int left = 0, right = gridColSize[i];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (grid[i][mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        count += left;
    }
    return count;
}

int solution(int** grid, int gridSize, int* gridColSize) {
    int totalElements = 0;
    for (int i = 0; i < gridSize; i++) {
        totalElements += gridColSize[i];
    }
    int medianPos = totalElements / 2;
    
    // Find min and max values
    int minVal = INT_MAX, maxVal = INT_MIN;
    for (int i = 0; i < gridSize; i++) {
        if (grid[i][0] < minVal) minVal = grid[i][0];
        if (grid[i][gridColSize[i]-1] > maxVal) maxVal = grid[i][gridColSize[i]-1];
    }
    
    // Binary search on answer
    int left = minVal, right = maxVal;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (countLessEqual(grid, gridSize, gridColSize, mid) <= medianPos) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

int main() {
    // Simple parsing for demonstration
    int grid[3][3] = {{1,3,5},{2,6,9},{3,6,9}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int gridColSize[3] = {3, 3, 3};
    
    int result = solution(gridPtr, 3, gridColSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m * log(max-min) * log n)

For each of log(max-min) binary search iterations, we do m binary searches on rows of size n

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler