Good problem, similar to Matrix median problem


#1

Very similar to the Matrix median problem. Some crazy corner cases though. Make sure you consider empty and singleton sets.


#2

can you explain how do we incorporate median for total number of elements as even, because in case of matrix median it was given that r*c is odd, how to we do it here?.


#3

Let’s say total elements = 10(even).
Target = 10/2 = 5.
You binary search and find a number whose lower_bound gives 5 or >= 5 as value.
We’ve found one of our medians.

But this is an even case, we need to find one more to take average. Now repeat the same
process, but this time take target=6 instead of 5. It’ll work.


#4

did you get right answer by doing it , i tried but coudnot solve because there was a case where elements were like 0 1 2 2 4 4 now i couldnot find second 2 by doing upper_bound


#5

Yes i get the right answer by doing this.

typedef long long ll;
ll cntBelow(const vector<int> &A, const vector<int> &B, ll mid) {
ll ind1 = upper_bound(A.begin(), A.end(), mid) - A.begin();
ll ind2 = upper_bound(B.begin(), B.end(), mid) - B.begin();
return (ind1 + ind2);   
}
double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
ll n = A.size(), m = B.size();
if(n == 0) {
    if(m%2 == 0) {
        return (B[m/2 -1] + B[m/2])/2.0;
    }
    return B[m/2];
}
if(m == 0) {
    if(n%2 == 0) {
        return (A[n/2 -1] + A[n/2])/2.0;
    }
    return A[n/2];
}
ll num = (n+m)/2;
ll mini = (A[0] > B[0] ? B[0] : A[0]), maxi = (A[n-1] > B[m-1] ? A[n-1] : B[m-1]);
while(mini <= maxi) {
    ll mid = (mini + maxi)/2;
    
    ll cnt = cntBelow(A, B, mid);
    if(cnt <= num) {
        mini = mid+1;   
    }
    else maxi = mid-1;
}
if((n+m)%2 != 0) return mini;
ll ans = mini;
mini = A[0] > B[0] ? B[0] : A[0];
maxi = A[n-1] > B[m-1] ? A[n-1] : B[m-1];
while(mini <= maxi) {
    ll mid = (mini + maxi) /2;
    
    ll cnt = cntBelow(A, B, mid);
    if(cnt < num) {
        mini = mid+1;   
    }
    else maxi = mid-1;
}
return (ans + mini)/2.0;
}