> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/binary-searching-and-sorting/matrix-median.md).

# Matrix Median

Given a matrix of integers **A** of size **N x M** in which each row is sorted.

Find an return the overall median of the matrix **A**.

**Note:** No extra memory is allowed.

**Note:** Rows are numbered from top to bottom and columns are numbered from left to right.

\
\
**Input Format**

```
The first and only argument given is the integer matrix A.
```

**Output Format**

```
Return the overall median of the matrix A.
```

**Constraints**

```
1 <= N, M <= 10^5
1 <= N*M  <= 10^6
1 <= A[i] <= 10^9
N*M is odd
```

**For Example**

```
Input 1:
    A = [   [1, 3, 5],
            [2, 6, 9],
            [3, 6, 9]   ]
Output 1:
    5
Explanation 1:
    A = [1, 2, 3, 3, 5, 6, 6, 9, 9]
    Median is 5. So, we return 5.

Input 2:
    A = [   [5, 17, 100]    ]
Output 2:
    17 
```

```java
public class Solution {
    public int findMedian(int[][] A) {
        int r = A.length, c = A[0].length;

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < r; i++) {
            min = Math.min(min, A[i][0]);
            max = Math.max(max, A[i][c - 1]);
        }
        // A median has (r*c/2) + 1 elements <= median (Including median)
        int desired = 1 + (r * c) / 2;
        while (min < max) {
            int mid = (min + max) / 2;
            // Find number of elements <= mid
            // We can reduce this step to RlogC, but it is not required here
            int count = smallerNumbers(mid, A);
            if (count < desired)
                min = mid + 1;
            else
                max = mid;
        }
        return min;
    }

    public int smallerNumbers(int k, int[][] A) {
        int r = A.length, c = A[0].length;
        int counter = 0;

        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                if (A[i][j] <= k)
                    counter = counter + 1;

        return counter;
    }
}
```