Old discuss is read-only now. Please go to New LeetCode Discuss for your questions and answers!

User account in old discuss will not integrate to the new one, but new discuss is integrated with new online judge, which means, if you already have an account in new online judge, you can access new discuss immediately!

If you want to ask for question relevant to the posts in old discuss, please copy content as part of your question, only old discuss link is NOT ALLOWED!

Please read the FAQ in new LeetCode Discuss to help yourself making the best use of Discuss!

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

asked 28 Mar '11, 02:23

1337c0d3r's gravatar image

1337c0d3r ♦♦
1.2k1489171
accept rate: 2%


Note:
Please head over to this MIT handout for a much better solution, although their solution does not deal with some special cases, which is easy to fix. Please consult Sophie's solution which fixes these special cases easily. Although my solution below works, it is too complicated.

Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++ code. If you are using other languages, you can still verify your solution by looking at the judge's test cases and its expected output.

Solution:
If you search this problem on Google, you will find tons of hits. However, most of them deal with the special case where m == n, and even so their code are filled with bugs. The CLRS book has this problem as exercise in section 9.3-8, however it also assumes the case where m == n. The only reliable solution I found on the web which deals with the generic case also seemed incorrect, as their definition of the median is the single middle element (although their approach of using binary search is pretty neat). According to the definition of the median, if (m + n) is even, then the median should be the mean of the two middle numbers.

If you read my previous post: Find the k-th Smallest Element in the Union of Two Sorted Arrays, you know that this problem is somewhat similar. In fact, the problem of finding the median of two sorted arrays when (m + n) is odd can be thought of solving the special case where k=(m+n)/2. Although we can still apply the finding k-th smallest algorithm twice to find the two middle numbers when (m + n) is even, it is no more a desirable solution due to inefficiency.

You might ask: Why not adapt the previous solution to this problem? After all, the previous algorithm solves a more general case. Well, I've tried that and I didn't consider the previous solution is easily adaptable to this problem. The main reason is because when (m + n) is even, the two middle elements might be located in the same array. This complicates the algorithm and many special cases have to be dealt in a case by case basis.

Similar to finding the k-th smallest, the divide and conquer method is a natural approach to this problem. First, we choose Ai and Bj (the middle elements of A and B) where i and j are defined as m/2 and n/2. We made an observation that if Ai <= Bj, then the median must be somewhere between Ai and Bj (inclusive). Therefore, we could dispose a total of i elements from left of Ai and a total of n-j-1 elements to the right of Bj. Please take extra caution not to dispose Ai or Bj, as we might need two middle values to calculate the median (it might also be possible that the two middle values are both in the same array). The case where Ai > Bj is similar.


Two sorted arrays A and B. i is chosen as m/2 and j is chosen as n/2. Ai and Bj are middle elements of A and B. If Ai < Bj, then the median must be between Ai and Bj (inclusive). Similarly with the opposite.

The main idea illustrated above is mostly right, however there is one more important invariant we have to maintain. It is entirely possible that the number of elements being disposed from each array is different. Look at the example above: If Ai <= Bj, two elements to the left of Ai and three elements to the right of Bj are being disposed. Notice that this is no longer a valid sub-problem, as both sub-array's median is no longer the original median.

Therefore, an important invariant we have to maintain is:

The number of elements being disposed from each array must be the same.

This could be easily achieved by choosing the number of elements to dispose from each array to be (Warning: The below condition fails to handle an edge case, for more details see the EDIT section below):

k = min(i, n-j-1) when Ai <= Bj.                   <--- 1(a
k = min(m-i-1, j) when Ai > Bj.                    <--- 1(b

Figuring out how to subdivide the problem is actually the easy part. The hard part is figuring out the base case. (ie, when should we stop subdividing?)

It is obvious that when m=1 or n=1, you must treat it as a special base case, or else it would end up in an infinite loop. The hard part is reasoning why m=2 or n=2 requires special case handling as well. (Hint: The two middle elements might be in the same array.)

Finally, implementing the above idea turns out to be an extremely tricky coding exercise. Before looking at the solution below, try to challenge yourself by coding the algorithm.

If you have a more elegant code to this problem, I would love to hear from you!

EDIT:
Thanks to Algorist for being the first person who points out a bug. (For more details, read his comment). The bug is caused by some edge cases that are not handled in the base case.

Shortly after I fixed that bug, I discovered another edge case myself which my previous code failed to handle.

An example of one of the edge cases is:

A = { 1, 2, 4, 8, 9, 10 }
B = { 3, 5, 6, 7 }

The above conditions ( 1(a), 1(b) ) fails to handle the above edge case, which returns 5 as the median while the correct answer should be 5.5.

The reason is because the number 5 is discarded in the first iteration, while it should be considered in the final evaluation step of the median. To resolve this edge case, we have to be careful not to discard the neighbor element when its size is even. Here are the corrected conditions ( 2(a), 2(b), 2(c), 2(d) ) for k which resolves this edge case.

k = min(i-1, n-j-1) when Ai <= Bj and m is even.   <--- 2(a)
k = min(i, n-j-1)   when Ai <= Bj and m is odd.    <--- 2(b)
k = min(m-i-1, j-1) when Ai > Bj  and n is even.   <--- 2(c)
k = min(m-i-1, j)   when Ai > Bj  and n is odd.    <--- 2(d)
Below is the bug-free code after going through a lengthy rigorous testing of all possible edge cases. (Not for the faint of heart!)

double findMedianBaseCase(int med, int C[], int n) {
    if (n == 1)
        return (med+C[0])/2.0;

    if (n % 2 == 0) {
        int a = C[n/2 - 1], b = C[n/2];
        if (med <= a)
            return a;
        else if (med <= b)
            return med;
        else /* med > b */
            return b;
    } else {
        int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
        if (med <= a)
            return (a+b) / 2.0;
        else if (med <= c)
            return (med+b) / 2.0;
        else /* med > c */
            return (b+c) / 2.0;
    }
}

double findMedianBaseCase2(int med1, int med2, int C[], int n) {
    if (n % 2 == 0) {
        int a = (((n/2-2) >= 0) ? C[n/2 - 2] : INT_MIN);
        int b = C[n/2 - 1], c = C[n/2];
        int d = (((n/2 + 1) <= n-1) ? C[n/2 + 1] : INT_MAX);
        if (med2 <= b)
            return (b+max(med2,a)) / 2.0;
        else if (med1 <= b)
            return (b+min(med2,c)) / 2.0;
        else if (med1 >= c)
            return (c+min(med1,d)) / 2.0;
        else if (med2 >= c)
            return (c+max(med1,b)) / 2.0;
        else  /* a < med1 <= med2 < b */
            return (med1+med2) / 2.0;
    } else {
        int a = C[n/2 - 1], b = C[n/2], c = C[n/2 + 1];
        if (med1 >= b)
            return min(med1, c);
        else if (med2 <= b)
            return max(med2, a);
        else  /* med1 < b < med2 */
            return b;
    }
}

double findMedianSingleArray(int A[], int n) {
    assert(n > 0);
    return ((n%2 == 1) ? A[n/2] : (A[n/2-1]+A[n/2])/2.0);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    assert(m+n >= 1);
    if (m == 0)
        return findMedianSingleArray(B, n);
    else if (n == 0)
        return findMedianSingleArray(A, m);
    else if (m == 1)
        return findMedianBaseCase(A[0], B, n);
    else if (n == 1)
        return findMedianBaseCase(B[0], A, m);
    else if (m == 2)
        return findMedianBaseCase2(A[0], A[1], B, n);
    else if (n == 2)
        return findMedianBaseCase2(B[0], B[1], A, m);

    int i = m/2, j = n/2, k;
    if (A[i] <= B[j]) {
        k = ((m%2 == 0) ? min(i-1, n-j-1) : min(i, n-j-1));
        assert(k > 0);
        return findMedianSortedArrays(A+k, m-k, B, n-k);
    } else {
        k = ((n%2 == 0) ? min(m-i-1, j-1) : min(m-i-1, j));
        assert(k > 0);
        return findMedianSortedArrays(A, m-k, B+k, n-k);
    }
}

EDIT2:
A reader buried.shopno had managed to code the solution more elegantly! I especially like how medianOfThree and medianOfFour were implemented. For more details, read his comment below. Great job!

Further thoughts:
A reader nimin98 suggested that the base case can be handled by simply doing a direct merge. In other words, we have to merge the short array (containing either one or two elements) with the longer array (pick the four elements near the middle. Deciding which four is another tricky business because of multiple special cases). nimin98's code has few bugs in the handling of base case.

In general, The above approaches (including mine) to handle the base case are not recommended due to tricky implementation. How about Binary Search? We can use binary search to find the correct position to insert elements from the shorter array into the longer array, thus completing the merge (You don't have to actually insert it, recording its index should be suffice).

link

answered 28 Mar '11, 02:23

1337c0d3r's gravatar image

1337c0d3r ♦♦
1.2k1489171
accept rate: 2%

class Solution {

public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int total = m + n;
    if (0 == total % 2) {
        return (FindKth(A, m, B, n, total/2) + FindKth(A, m, B, n, total/2 + 1)) / 2;
    } else {
        return FindKth(A, m, B, n, total/2 + 1);
    }
}

double FindKth(int A[], int m, int B[], int n, int k) {
    if (m > n) return FindKth(B, n, A, m, k);
    if (0 == m) return B[k-1];
    if (0 == n) return A[k-1];
    if (1 == k) return min(A[0], B[0]);

    int aMid = min(k/2, m);
    int bMid = k - aMid;
    if (A[aMid-1] < B[bMid-1]) {
        return FindKth(A + aMid, m - aMid, B, n, k - aMid);
    } else {
        return FindKth(A, m, B + bMid, n - bMid, k - bMid);
    }
}

};

link

answered 20 Aug '13, 07:16

weibest's gravatar image

weibest
312
accept rate: 0%

class Solution {
public:
    double MedianOfFour (int a, int b, int c, int d)
{
        int minValue = min (d, min (a, min (b,c) ) );
        int maxValue = max (d, max (a, max (b,c) ) );
        return (a + b + c + d - minValue - maxValue) / 2.0 ;
}

double MedianOfThree (int a, int b, int c)
{
        int minValue = min (a, min (b,c) ) ;
        int maxValue = max (a, max (b,c) ) ;
        return (a + b + c - minValue - maxValue);
}

//constraint : n <= m
double MedianSortedArrays (int A[], int n, int B[], int m)
{
        //base case # 0
        if(n==0)
        {       
               if(m%2==1)return B[m/2];
              else return (B[m/2-1]+B[m/2])/2.0;
        }
        //base case # 1
        if ( n == 1 ) 
        {
                if ( m == 1 ) 
                        return (A[0] + B[0]) / 2.0; 
                if ( m % 2 == 1) 
                         return ( B[m/2] + MedianOfThree (A[0], B[m/2-1], B[m/2+1]) ) / 2.0 ;
                else 
                        return MedianOfThree ( A[0], B[m/2-1], B[m/2] );
        }

        //base case # 2
        if ( n == 2 ) 
        {
                if ( m == 2 )
                        return MedianOfFour (A[0], A[1], B[0], B[1]);
                if ( m % 2 == 1 )
                        return MedianOfThree ( B[m/2], min(A[0], B[m/2+1]), max (A[1], B[m/2-1]) ) ;
                else 
                        return MedianOfFour ( B[m/2-1], B[m/2], min(A[0], B[m/2+1]), max(A[1], B[m/2-2]) );
        }

        int minRemoved, idxA = n/2 , idxB = m/2 ;

        if ( A[idxA] < B[idxB]  )                                               
        {
                if ( n % 2 == 0 ) --idxA;       //for even number of elements --idxA points to lower median of A[]
                minRemoved = min ( idxA, m - idxB - 1) ;        
                return MedianSortedArrays ( A + minRemoved, n - minRemoved, B, m - minRemoved); 
        }
        else                                                                                    
        {
                if ( m % 2 == 0 ) --idxB;       //for even number of elements --idxB points to lower median of B[]
                minRemoved = min ( n - idxA - 1, idxB) ;        
                return MedianSortedArrays ( A, n - minRemoved, B + minRemoved, m - minRemoved); 
        }

}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(m<=n)return MedianSortedArrays(A,m,B,n);
        else return MedianSortedArrays(B,n,A,m);
    }
};
Thank you: http://ideone.com/FtqjM
I have learned a lot from this problem.
link

answered 16 Jan '13, 03:21

sillyjims's gravatar image

sillyjims
9614
accept rate: 0%

edited 16 Jan '13, 03:23

A java implementation based on MIT handout.

I just realized that the algorithm given in comments (http://leetcode.com/2011/03/median-of-two-sorted-arrays.html#comment-1053) didn't validate index of B[j] (in the case where m+n is even.

Also, the mod can be replaced with bit-operation, which is much cheaper.

private double findMedian(int A[], int B[], int left, int right) {
    int m = A.length, n = B.length, mid = (m+n)/2;
    if (left > right) {
        return findMedian(B, A, Math.max(0, mid-m), Math.min(n-1, mid));
    }

    int i = (left+right) / 2, j = mid - i - 1;
    if (j >= 0 && A[i] < B[j])  // A[i] < median
        return findMedian(A, B, i+1, right);
    if (j < n-1 && A[i] > B[j+1])  // A[i] > median
        return findMedian(A, B, left, i-1);
    // found median
    // m+n is odd
    if ( ((m+n) & 0x1) > 0 || (i <= 0 && (j < 0 || j >= n)))
        return A[i];
    // m+n is even
    if (j < 0 || j >= n)
        return (A[i] + A[i-1]) / 2.0;
    if (i <= 0)
        return (A[i] + B[j]) / 2.0;
    return (A[i] + Math.max(B[j], A[i-1])) / 2.0;
}

public double findMedianSortedArrays(int A[], int B[]) {
    int m = A.length, n = B.length, mid = (m+n)/2;
    if (m<n)
        return findMedian(A, B, Math.max(0, mid-n), Math.min(m-1, mid));
    else
        return findMedian(B, A, Math.max(0, mid-m), Math.min(n-1, mid));
}
link

answered 09 Apr '13, 00:48

n00tc0d3r's gravatar image

n00tc0d3r
32625
accept rate: 0%

edited 09 Apr '13, 00:54

class Solution {
public:
    double findMedian(int A[], int B[], int l, int r, int nA, int nB) {
        if (l>r) 
            return findMedian(B, A, max(0, (nA+nB)/2-nA), min(nB-1, (nA+nB)/2), nB, nA);

        int i = (l+r)/2;
        int j = (nA+nB)/2 - i - 1;

        if (j>=0 && A[i] < B[j]) return findMedian(A, B, i+1, r, nA, nB);
        else if (j<nB-1 && A[i] > B[j+1]) return findMedian(A, B, l, i-1, nA, nB);
        else {
            if ( (nA+nB)%2 == 1 ) return A[i];
            if (i>0) {
                int pre = (j < 0) ? A[i - 1] : max(B[j], A[i-1]);
                return (A[i]+pre)/2.0;
            }
            return (A[i]+B[j])/2.0;
        }
    }

    double findMedianSortedArrays(int A[], int n, int B[], int m) {     
        return findMedian(A, B, max(0, (m+n)/2-m), min(n-1, (m+n)/2), n, m);
    }
};
link

answered 15 Jun '13, 14:51

xiaoc10's gravatar image

xiaoc10
112
accept rate: 0%

edited 16 Jun '13, 09:28

@1337c0d3r

This solution is greatly inspired by the Manacher's algorithm which is described longest palindromic substring. By inject the median of two ajacent numbers in the array, we don't need to take the array's oddness into consideration.

Given two sorted arrays Small and Big, Small.size()<= Big.size(). For example Small= {1,2,3,4}, Big = {5,6,7,8}

Inflated Small is {1,1.5,2,2.5,3,3.5,4} and inflated Big is {5,5.5,6,6.5,7,7.5,8}. Constructing the inflated arrays would require O(n),which is undesirable. We can use the function get(int[] array,pos) to get array[pos] whenever we need such a value,see the following codes. We just call the array inflated Small as small and inflated big as big for simplicity.

The tricky part is that we can constantly reduce the size of small and big by the same offset untill the length of small is 1 or 3. Why? Because Small (the base of inflated Small or small) at most contribute two elements that determines the final median.

When the size of small and big are small enough we can easily compute the median by simply sorting them. In this program, the size of small is constantly reduced by approximately half. By approximately I mean the two numbers neighboring the median of small is never changed in each round. (Notice the length of small or inflated Small is always odd, so there always exists a median).

while(size of small >3) {

if the median of small == the median of big
    return the median of small
if the median of small < the median of big{
    cut the left half of small        // the median and the neibors besides it are not removed.
    and the number of cutted small N  // N = (small.leng-3)/2*2;
    cut N from the right of big       // the size of big is always bigger
}
else
        do the opposite

}

When the above loop is done, the size of big can still be very big. You can prove that the median of small and the 5 elements closest to the center of B is the median of the two sorted array.

public class Solution {
   public double get(int[] A, int pos){
        return (pos%2==0)?A[pos/2]:((double)(A[pos/2]+A[pos/2+1])/2);
    }

   public double  findMidian(int S[],int sStart,int sEnd,int B[],int bStart, int bEnd){
        ArrayList<Double> list = new ArrayList<Double>();
        for(int i = sStart; i<= sEnd; i++)
            if(i%2==0)
                list.add(get(S,i));
        for(int i = bStart; i <= bEnd; i++)
            if(i%2==0)
                list.add(get(B,i));

        double [] array = new double [list.size()];
        for(int i = 0; i < list.size();i++)
            array[i] = list.get(i);
        Arrays.sort(array);
        if(array.length%2==0)
            return (double)(array[array.length/2-1]+array[array.length/2])/2;
        else
            return array[array.length/2];
    }
    public double findMedianSortedArrays(int A[], int B[]) {
        int [] small, big;
        small = (A.length>=B.length)?B:A;
        big = (small==B)?A:B;

        int sStart = 0, sEnd = 2*small.length-2,bStart = 0, bEnd = 2*big.length-2;

        while(sEnd - sStart >2){
            int sMidPos = (sStart+sEnd)/2;
            double sMid = get(small,sMidPos);
            int bMidPos = (bStart+bEnd)/2;
            double bMid = get(big,bMidPos);

            int offset = (sMidPos)/2*2-sStart;
            if(sMid<bMid){
                sStart+=offset;
                bEnd-=offset;
                continue;
            }
            if(sMid == bMid)
                return sMid;

            sEnd-=offset;
            bStart+=offset;
        }

        int middle = (bEnd+bStart)/2;
        if(middle-4>=bStart)
            return findMidian(small,sStart,sEnd,big,bStart+2,bEnd-2);
        return findMidian(small,sStart,sEnd,big,bStart,bEnd);
    }
link

answered 09 May '13, 18:30

yangmo's gravatar image

yangmo
113
accept rate: 0%

seems the comment:

/* a < med1 <= med2 < b */

should be:

/* b < med1 <= med2 < c */
link

answered 15 Jul '13, 18:12

steve's gravatar image

steve
113
accept rate: 0%

edited 15 Jul '13, 18:13

 public double findMedianSortedArrays(int A[], int B[]) {
    int a=0,b=0,result=0,odd=0;
    boolean IsOdd=false;
    if((A.length+B.length)%2==0)
        IsOdd=true;
    for(int i=0;i<(A.length+B.length)/2+1;i++)
    {
        if(b==B.length)
            result=A[a++];
        else if(a==A.length)
            result=B[b++];
        else
        {
            if((A[a]>B[b]))
                result=B[b++];
            else
                result=A[a++];
        }
        if(IsOdd&&i+1==(A.length+B.length)/2)
            odd=result;

    }
    return IsOdd?((double)result+(double)odd)/2:(double)result;
}
link

answered 02 Aug '13, 15:24

cheninnerv's gravatar image

cheninnerv
113
accept rate: 0%

A simpler solution without recursion. O(log(m+n)).

 public double findMedianSortedArrays(int A[], int B[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (A == null)  A = new int[0];
        if (B == null)  B = new int[0];
        int nA = A.length;
        int nB = B.length;
        if (nA == 0 && nB == 0) return Integer.MIN_VALUE;

        int k = (nA + nB) / 2;
        int l = k - Math.min(k, nB);
        int r = Math.min(k, nA);

        while(l <= r) {
            int i = l + (r - l) / 2;
            int j = k - i;
            int a_i = (i < nA) ? A[i] : Integer.MAX_VALUE;
            int a_i_prev = (i > 0) ? A[i-1] : Integer.MIN_VALUE;
            int b_j = (j < nB) ? B[j] : Integer.MAX_VALUE;
            int b_j_prev = (j > 0) ? B[j-1] : Integer.MIN_VALUE;

            if (a_i >= b_j_prev && b_j >= a_i_prev) {
                if (((nA + nB) & 1) == 1) {
                    return Math.min(a_i, b_j);
                } else {
                    return (Math.min(a_i, b_j) + Math.max(a_i_prev, b_j_prev)) / 2.0;
                }
            }

            if (a_i < b_j_prev) {
                l = i + 1;
            } else {
                r = i - 1;
            }
        }

        return Integer.MIN_VALUE;
    }
link

answered 02 Oct '13, 03:39

zhangxu's gravatar image

zhangxu
112
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • Indent code by 4 spaces.
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×133

Asked: 28 Mar '11, 02:23

Seen: 7,398 times

Last updated: 02 Oct '13, 03:39