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:
- Initialize
low
to the minimum possible value (1
) andhigh
to the maximum possible value (1e9
). - Enter a loop that continues as long as
low
is less than or equal tohigh
. - Calculate the
mid
value using(low + high) / 2
. - Initialize
cnt
to track the number of elements less than or equal tomid
. - Iterate through each row of the matrix and call the
countSmaller
function to count elements less than or equal tomid
. - Compare the total count (
cnt
) with the required count to determine whether the median is to the left or right of the currentmid
. - If the count is less than or equal to
(n * m) / 2
, adjust thelow
bound to the right by settinglow = mid + 1
. - If the count is greater than
(n * m) / 2
, adjust thehigh
bound to the left by settinghigh = mid - 1
. - Repeat steps 3-8 until
low
is no longer less than or equal tohigh
. - 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:
Complexity | Notation | Explanation |
---|---|---|
Time | O(N*logM) | |
Space | O(1) | The algorithm uses a constant extra space |
Top comments (0)