0
\$\begingroup\$

The task is to find the median of two Arrays. I have an O(n) solution. Can it be written in a better time complexity?

def findMedianSortedArrays(self, A, B):
    combined = []
    while len(A) > 0 and len(B) > 0:
        if (A[0] < B[0]):
            combined.append(A.pop(0))
        else:
            combined.append(B.pop(0))
    combined.extend(A)
    combined.extend(B)

    length = len(combined)
    if length % 2 != 0:
        return combined[length // 2]
    else:
        return (combined[length // 2-1] + combined[length//2]) / 2
\$\endgroup\$
2
\$\begingroup\$

According to the Style Guide for Python Code, function and variable names should be “lowercase, with words separated by underscores as necessary to improve readability.” In your case I'd suggest

def median_of_sorted_arrays(a, b):

Your code determines the median correctly. However, it modifies the passed arguments, which might be unexpected to the caller:

a = [-5, 3, 6, 12, 15]
b = [-12, -10, -6, -3, 4, 10]

print(findMedianSortedArrays(a, b))   # prints 3
print(findMedianSortedArrays(a, b))   # prints 13.5

This could be fixed by accessing the lists via subscripting:

i = 0
j = 0
while i < len(a) and j < len(b):
    if (a[i] < b[j]):
        combined.append(a[i])
        i += 1
    else:
        combined.append(b[j])
        j += 1
combined.extend(a[i:])
combined.extend(b[j:])

The next possible improvement is to get rid of the additional storage: Instead of storing elements from a or b into the combined list you could just count how many elements have been merged so far, until the median element is found.

A more efficient algorithm is described in

The basic idea is to partition both a and b into

a[:i] + a[i:]
b[:j] + b[j:]

such that the following conditions are satisfied:

i + j = (len(a) + len(b) + 1) // 2
a[i-1] <= b[j]
b[j-1] <= a[i]

and this can be done efficiently with a binary search. Then the “union” of the first (resp. second) halves is the first (resp. second) half of the combined array, so that the median is

max(a[i - 1], b[j - 1])   # if the total length is odd
(max(a[i - 1], b[j - 1]) + min(a[i], b[j])) / 2 # if the total length is even
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.