DAY 83 - MATRIX MEDIAN
Tags: leetcode, beginners, coding, algorithms
Published: 2023-08-25 18:10:32

Hey Guys! Welcome to day 83 and we are going to solve today another leetcode problem.

## Question: [_Matrix Median_](https://www.interviewbit.com/problems/matrix-median/)

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

Find and return the overall median of matrix `A`.

- **NOTE:** No extra memory is allowed.
- **NOTE:** Rows are numbered from top to bottom and columns are numbered from left to right.

---

### Example 1:

> - **Input:** A = [   [1, 3, 5],
        [2, 6, 9],
        [3, 6, 9]   ]
> - **Output :** 5

---

## Intuition:
- Whenever we want to search things, our mind should immediately think of a case where something can be found using binary search. Also in cases where we are given something sorted, it will most likely use a binary search type approach.

Here we have to find the median and we have been given row wise sorted matrix. So we will apply binary search here but how?.
Let's go through the algorithm first, as it will help us build intuition and make it clear why we did it.

### Algorithm:
The approach employs a binary search-like technique to find the median value within a specified range of possible values. The steps involve:

1. Initialize `low` to the minimum possible value (`1`) and `high` to the maximum possible value (`1e9`).
2. Enter a loop that continues as long as `low` is less than or equal to `high`.
3. Calculate the `mid` value using `(low + high) / 2`.
4. Initialize `cnt` to track the number of elements less than or equal to `mid`.
5. Iterate through each row of the matrix and call the `countSmaller` function to count elements less than or equal to `mid`.
6. Compare the total count (`cnt`) with the required count to determine whether the median is to the left or right of the current `mid`.
7. If the count is less than or equal to `(n * m) / 2`, adjust the `low` bound to the right by setting `low = mid + 1`.
8. If the count is greater than `(n * m) / 2`, adjust the `high` bound to the left by setting `high = mid - 1`.
9. Repeat steps 3-8 until `low` is no longer less than or equal to `high`.
10. Return `low - 1` as the final value to get the correct median value.

### Breakdown:
- Suppose we were given a sorted array of n * m elements. it's median would be somewhere around it's mid. We can't find the fully sorted matrix without using extra space.
- But what we can do is find how many elements are lesser than our current element.
- Say there are 9 elements, it's median would be on 4th position.
- If we can find the element which has just 3 elements lesser than equal to it we have found our median.

---

**Code:**

```cpp
int countSmaller(vector<int> &arr, int mid) {
    int count = 0;
    for (int num : arr) {
        if (num <= mid) {
            count++;
        }
    }
    return count;
}

int Solution::findMedian(vector<vector<int> > &A) {
    int low = 1;
    int high = 1e9;
    
    int mid;
    int n = A.size();
    int m = A[0].size();
    
    while (low <= high) {
        mid = low + (high - low) / 2;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += countSmaller(A[i], mid);
        }
        
        if (cnt <= (n * m) / 2) {  // Adjusted the condition to find the median
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;  // Subtracting 1 to get the correct median value
}


```

### Complexity Analysis:

| Complexity | Notation | Explanation |
|------------|----------|-------------|
| Time       | O(N*logM) |  |
| Space      | O(1)     | The algorithm uses a constant extra space|