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 k^{th} order statistic – the k^{th} 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 k^{th} 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 k^{th} order statistic and all elements in B[pb+1..M] lie after the k^{th} order statistic. We can reduce the search to finding k-pa^{th} 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 k^{th} order statistic and all elements in A[pa+1..N] lie after the k^{th} order statistic. We can reduce the search to finding k-pb^{th} 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 k^{th} 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:

### Like this:

Like Loading...

*Related*

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.