DAY 83 - MATRIX MEDIAN

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

Question: 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:

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: