Find median value of two Sorted Arrays

Question

To improve my coding knowledge can you please give me suggested changes on my code?

class Solution(object):
    def findMedianSortedArrays(self, list1, list2):
        merged_array = list1 + list2
        merged_array.sort()
        length = len(merged_array)
        medians = length%2
        median = length/2
        if medians!=0:
            median = int(median)
            calculation = merged_array[median] 
            return calculation
        else:
            median = int(median)
            first = merged_array[median]
            second = merged_array[median-1]
            calculation = (second+first)
            calculation = calculation/2.0
            return calculation

LEETCODE

Answer 1

context

You likely obtained the problem statement from leetcode or similar. It would be helpful to share its text and the URL.

PEP-8

    def findMedianSortedArrays(self, list1, list2):

PEP-8 asks that you spell this find_median_sorted_arrays. But I suspect that a polyglot site like leetcode is requiring you to fit a mold that makes sense for other languages, like {JS, java, pascal}, and thus is forcing you to adopt camelCase.

class Solution(object):

Nowadays, in python3, this is just silly. Everything inherits from object, and you don't need to distinguish between old style and new style classses any more. Prefer:

class Solution:

sorted

        merged_array = list1 + list2
        merged_array.sort()

Prefer to use the sorted() builtin:

        merged_array = sorted(list1 + list2)

And it's not an array -- it's a merged list.

meaningful identifier

        medians = length % 2
        median = length / 2

These are unhelpful names. It's unclear why an {odd, even} flag would be plural median. And median clearly isn't one; it is an index that can yield a median value.

The pair of subsequent int(median) expressions make it pretty clear that you instead intended to assign:

        median = length // 2

anonymous intermediate expression

Introducing a temp var with an uninformative name, calculation, does not help the Gentle Reader.

            calculation = merged_array[median] 
            return calculation
        else:
            median = int(median)
            first = merged_array[median]
            second = merged_array[median-1]
            calculation = (second+first)
            calculation = calculation/2.0
            return calculation

In the if clause, better to just return merged_array[median].

In the else clause, better to
return (merged_array[median] + merged_array[median-1]) / 2.

An index named mid, rather than median, would be conventional here.

This expression blows up if caller offered an empty list, and that's OK. Caller will get what they deserve.

If you really want to introduce a named temp result in the else clause, at least call it mean.

Answer 2

Solve problems by breaking them down into simpler parts. Your solution mixes several distinct parts of the calculation: (1) merging the lists into a sorted list, (2) finding the middle value(s), and (3) computing the mean of those middle values. You can write more readable and intuitve code by keeping those parts separate, each in their own narrowly tailored function. At the top level, we want a function to find the median of one or more sequences.

def median_seqs(*seqs):
    return median(merged(seqs))

Merge the sequences. Merging is fairly easy to do: start with an empty list; append the values in each sequence to the list, which can be done with xs.extend(); sort and return.

def merged(*seqs):
    xs = []
    ...

Compute a median. Your current code has more variables and conditional logic than seem necessary. The key to finding a median is to get the middle values, which we could grab via a slice into the list if we could calculate the needed indexes. That can be done if you know the list size, have an index of a value approximately at the middle (i = size // 2), and have a boolean flag that is true for even-sized lists. Once you have those middle values, return their mean.

def median(xs):
    # xs              | size | i | middle
    # --------------------------------------
    # [0, 11, 22, 33] | 4    | 2 | xs[1:3]
    # [0, 11, 22]     | 3    | 1 | xs[1:2]
    ...
    middle_vals = xs[...]
    return mean(middle_vals)

Keep breaking things down: the mean. Don't compute a mean in your median() function. Code tends to be simpler and easier to understand at a glance by delegating lower-level details to other functions.

def mean(xs):
    if xs:
        return sum(xs) / len(xs)
    else:
        raise ValueError('mean() requires at least one value')

Possible next step: a new algorithm. As noted in a comment, you don't need to merge and sort the sequences. They are already sorted. With some binary-search you should be able to find the middle values more quickly. [Before bothering with that, ask whether you care about code execution speed in this context -- maybe yes, maybe no.]

Answer 3

I'm not a Python dev, but I do think that I have some insights that transcend language that may help you.

        merged_array = list1 + list2
        merged_array.sort()

Since this is a programming challenge, we can guess that performance will be measured. From a performance standpoint, this is a horrible way to merge two sorted lists. In general, sort in any language will be a linearlogarithmic sort (\$\mathcal{O}(n\log{n})\$). But if the inputs are two sorted lists, there is a linear time merge that will produce a sorted list.

The truth is that you don't actually need the merged list. All you need to do is to find the element that would be in the middle spot. There is a relatively straightforward solution that works in linear time (\$\mathcal{O}(n)\$). Have a single loop over both lists until you find the element that would be at the middle point of the combined list.

Start with two list indexes pointing to the first position of each list. Compare the elements at the indexed points. Increment the index pointing at the smaller element (if the same size, pick either). You know how long each list is, so you can calculate the length of the combined list. When the sum of the two indexes is equal to the middle point of the combined list, return the correct element and you're done.

Even that doesn't seem like the most efficient solution. That's still linear. If you had a single sorted list, you could find the median in constant time. With two lists, I suspect that it is possible in logarithmic time by using something similar to a binary search to find the element that would be in the middle point of the combined list. I.e. rather than start at the beginning of the lists, start the indexes at the middle of each list. Now, when you find the smaller element, you can use that as a lower bound for the location of the median in that list. And the larger element is the upper bound in that list.

I've left out a few steps. Perhaps I should claim that this is for didactic purposes so that you can learn yourself. But actually I just don't feel like implementing this at the moment. Hopefully this is enough to point you at the two suggested solutions (linear and logarithmic time solutions). It's possible that you might be able to get as good as \$\mathcal{O}(\log{\log{n}})\$. Doing that asymptotic analysis would also be a good exercise.