Median of 5 sorted arrays
I am trying to find the solution for median of 5 sorted arrays. This was an interview questions.
The solution I could think of was merge the 5 arrays and then find the median [O(l+m+n+o+p)].
I know that for 2 sorted arrays of same size we can do it in log(2n). [by comparing the median of both arrays and then throwing out 1 half of each array and repeating the process]. .. Finding median can be constant time in sorted arrays .. so I think this is not log(n) ? .. what is the time complexity for this ?
1] Is there a similar solution for 5 arrays . What if the arrays are of same size , is there a better solution then ?
2] I assume since this was asked for 5, there would be some solution for N sorted arrays ?
Thanks for any pointers.
Some clarification/questions I asked back to the interviewer:
Are the arrays of same length
=> No
I guess there would be an overlap in the values of arrays
=> Yes
As an exercise, I think the logic for 2 arrays doesnt extend . Here is a try:
Applying the above logic of 2 arrays to say 3 arrays:
[3,7,9] [4,8,15] [2,3,9] ... medians 7,8,3
throw elements [3,7,9] [4,8] [3,9] .. medians 7,6,6
throw elements [3,7] [8] [9] ..medians 5,8,9 ...
throw elements [7] [8] [9] .. median = 8 ... This doesnt seem to be correct ?
The merge of sorted elements => [2,3,4,7,8,9,15] => expected median = 7
Answer
(This is a generalization of your idea for two arrays.)
If you start by looking at the five medians of the five arrays, obviously the overall median must be between the smallest and the largest of the five medians.
Proof goes something like this: If a is the min of the medians, and b is the max of the medians, then each array has less than half of its elements less than a and less than half of its elements greater than b. Result follows.
So in the array containing a, throw away numbers less than a; in the array containing b, throw away numbers greater than b... But only throw away the same number of elements from both arrays.
That is, if a is j elements from the start of its array, and b is k elements from the end of its array, you throw away the first min(j,k) elements from a's array and the last min(j,k) elements from b's array.
Iterate until you are down to 1 or 2 elements total.
Each of these operations (i.e., finding median of a sorted array and throwing away k elements from the start or end of an array) is constant time. So each iteration is constant time.
Each iteration throws away (more than) half the elements from at least one array, and you can only do that log(n) times for each of the five arrays... So the overall algorithm is log(n).
[Update]
As Himadri Choudhury points out in the comments, my solution is incomplete; there are a lot of details and corner cases to worry about. So, to flesh things out a bit...
For each of the five arrays R, define its "lower median" as R[n/2-1] and its "upper median" as R[n/2], where n is the number of elements in the array (and arrays are indexed from 0, and division by 2 rounds down).
Let "a" be the smallest of the lower medians, and "b" be the largest of the upper medians. If there are multiple arrays with the smallest lower median and/or multiple arrays with the largest upper median, choose a and b from different arrays (this is one of those corner cases).
Now, borrowing Himadri's suggestion: Erase all elements up to and including a from its array, and all elements down to and including b from its array, taking care to remove the same number of elements from both arrays. Note that a and b could be in the same array; but if so, they could not have the same value, because otherwise we would have been able to choose one of them from a different array. So it is OK if this step winds up throwing away elements from the start and end of the same array.
Iterate as long as you have three or more arrays. But once you are down to just one or two arrays, you have to change your strategy to be exclusive instead of inclusive; you only erase up to but not including a and down to but not including b. Continue like this as long as both of the remaining one or two arrays has at least three elements (guaranteeing you make progress).
Finally, you will reduce to a few cases, the trickiest of which is two arrays remaining, one of which has one or two elements. Now, if I asked you: "Given a sorted array plus one or two additional elements, find the median of all elements", I think you can do that in constant time. (Again, there are a bunch of details to hammer out, but the basic idea is that adding one or two elements to an array does not "push the median around" very much.)