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: