Median of 5 sorted arrays

Question

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 1

(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.)

Answer 2

Should be pretty straight to apply the same idea to 5 arrays.

First, convert the question to more general one. Finding Kth element in N sorted arrays

1. Find (K/N)th element in each sorted array with binary search, say K1, K2... KN

2. Kmin = min(K1 ... KN), Kmax = max(K1 ... KN)

3. Throw away all elements less than Kmin or larger than Kmax, say X elements has been thrown away.

4. Now repeat the process by find (K - X)th element in sorted arrays with remaining elements

Answer 3

You don't need to do a complete merge of the 5 arrays. You can do a merge sort until you have (l+n+o+p+q)/2 elements then you have the median value.

Answer 4

Finding the kth element in a list of sorted lists can be done by binary search.

from bisect import bisect_left
from bisect import bisect_right

def kthOfPiles(givenPiles, k, count):
    '''
    Perform binary search for kth element in  multiple sorted list

    parameters
    ==========
    givenPiles  are list of sorted list
    count   is the total number of
    k       is the target index in range [0..count-1]
    '''
    begins = [0 for pile in givenPiles]
    ends = [len(pile) for pile in givenPiles]
    #print('finding k=', k, 'count=', count)
    
    for pileidx,pivotpile in enumerate(givenPiles):
        
        while begins[pileidx] < ends[pileidx]:
            mid = (begins[pileidx]+ends[pileidx])>>1
            midval = pivotpile[mid]
            
            smaller_count = 0
            smaller_right_count = 0
            for pile in givenPiles:
                smaller_count += bisect_left(pile,midval)
                smaller_right_count += bisect_right(pile,midval)
                
            #print('check midval', midval,smaller_count,k,smaller_right_count)
            if smaller_count <= k and k < smaller_right_count:
                return midval
            elif smaller_count > k:
                ends[pileidx] = mid
            else:
                begins[pileidx] = mid+1
            
    return -1

def medianOfPiles(givenPiles,count=None):
    '''
    Find statistical median
    Parameters:
    givenPiles  are list of sorted list
    '''
    if not givenPiles:
        return -1 # cannot find median
    
    if count is None:
        count = 0
        for pile in givenPiles:
            count += len(pile)
            
    # get mid floor
    target_mid = count >> 1
    midval = kthOfPiles(givenPiles, target_mid, count)
    if 0 == (count&1):
        midval += kthOfPiles(givenPiles, target_mid-1, count)
        midval /= 2
        
    return '%.1f' % round(midval,1)

The code above gives correct-statistical median as well.

Coupling this above binary search with patience-sort, gives a valuable technique.

There is worth mentioning median of median algorithm for selecting pivot. It gives approximate value. I guess that is different from what we are asking here.

Answer 5

Use heapq to keep each list's minum candidates.

Prerequisite: N sorted K length list

O(NKlgN)

import heapq
class Solution:
    def f1(self, AS):
        def f(A): 
            n = len(A)
            m = n // 2
            if n % 2:
                return A[m]
            else:
                return (A[m - 1] + A[m]) / 2
        res = []
        q = []
        for i, A in enumerate(AS):
            q.append([A[0], i, 0])
        heapq.heapify(q)
        N, K = len(AS), len(AS[0])
        while len(res) < N * K:
            mn, i, ii = heapq.heappop(q)
            res.append(mn)
            if ii < K - 1:
                heapq.heappush(q, [AS[i][ii + 1], i, ii + 1])
        return f(res)

    def f2(self, AS):
        q = []
        for i, A in enumerate(AS):
            q.append([A[0], i, 0])
        heapq.heapify(q)
        N, K = len(AS), len(AS[0])
        n = N * K
        m = n // 2
        m1 = m2 = float('-inf')
        k = 0
        while k < N * K:
            mn, i, ii = heapq.heappop(q)
            res.append(mn)
            k += 1
            if k == m - 1:
                m1 = mn
            elif k == m:
                m2 = mn
                return m2 if n % 2 else (m1 + m2) / 2 
            if ii < K - 1:
                heapq.heappush(q, [AS[i][ii + 1], i, ii + 1])
        return 'should not go here'