Problem of the day: Median of two sorted arrays

Another interesting problem that I saw today: Given two sorted arrays, find their combined median (median of the array formed by merging both the arrays). If the number of elements in the combined array is even, then the average of the two middle elements is the median.

Let N and M be the sizes of the two arrays respectively. The trivial solution is to create a new array of size N+M, merge both arrays into it and return the middle (or average of the two middle) element(s). This has space complexity O(N+M) and time complexity O(N+M). We can, of course, do better. If you want to take a crack at this problem before looking at the solution, you can solve it at the link provided above.

It took me a great deal of time to solve this. We can generalize the problem of finding the median to finding the kth order statistic – the kth element in the sorted sequence. The median is (N+M)/2 + 1 order statistic (when N+M is odd) or the average of (N+M)/2 and (N+M)/2 + 1 order statistics (when N+M is even).

We can find the kth order statistic using binary search. Let’s split the array A at pa = k/2 and B at pb = k-pa. These two positions separate the combined left part (of size k) from the combined right part (of size k or k+1).

Assuming 1-based indexing for simplicity, if A[pa] <= B[pb], all elements in A[1..pa] lie before the kth order statistic and all elements in B[pb+1..M] lie after the kth order statistic. We can reduce the search to finding k-path order statistic in A[pa+1..N] and B[1..pb].

Similarly, if A[pa] > B[pb], all elements in B[1..pb] lie before the kth order statistic and all elements in A[pa+1..N] lie after the kth order statistic. We can reduce the search to finding k-pbth order statistic in A[1..pa] and B[pb+1..M].

The search terminates when either of the arrays becomes empty and we can just return the kth element in the second array or k becomes 1 and we can return the minimum of first elements in the two arrays. Since we get rid of half the elements at each step, the overall time complexity is O(log N+M).

Let’s work through an example;

Here’s the solution:

Advertisements

2 thoughts on “Problem of the day: Median of two sorted arrays

  1. How about recursion?
    Assume both arrays have at least 2 members. If not, the problem is trivial.
    1. Examine the first two elements of A and B, remove the smaller one from its array and note it as x. If both initial elements are the same, remove x from A only.
    2. Examine the last two elements of (the current) A and B, remove the larger one from its array and note it as y. If both initial elements are the same, remove y from A only.
    3. Recurse on the modified arrays A and B until one or more of them has only one member. Solve trivially for the median.

    • You don’t even need to check and remove the last elements. This is identical to maintaining two pointers at the start of the two arrays and incrementing the one pointing to the smaller value until you reach the median. This has complexity O(N+M). We can do better.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s