2
\$\begingroup\$

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

Challenge scoring:  beats 69.81% runtime and 13.6% memory

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

\$\endgroup\$
2
  • \$\begingroup\$ All Type of Review To Help Beginner \$\endgroup\$ Dec 22, 2023 at 3:23
  • 3
    \$\begingroup\$ The biggest problem with this code is a complexity. The space complexity is linear in terms of the combined length, and the time complexity is also at least linear. Try to think of a solution which runs in a constant space and a logarithmic time. Hint: use the fact that the input lists are already sorted. \$\endgroup\$
    – vnp
    Dec 22, 2023 at 5:11

3 Answers 3

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Disagree on the recommendation of using sorted (which needs to create a copy) over list.sort (which sorts in place). On leetcode in particular, answers with list.sort often edge out otherwise identical ones with sorted. \$\endgroup\$
    – Seb
    Dec 22, 2023 at 18:32
  • 1
    \$\begingroup\$ That's cool, I take your point. Reasonable people can agree to differ. Here it is due to different goals: speed vs readability. (And if "speed matters", then we should choose a language that isn't python.) OP is a junior dev, and I was trying to meet them where they are, encouraging the authoring of more readable / maintainable code. If those don't matter, then we should assign merged_array = list1 (constant, essentially zero cost) and .extend() it with list2 prior to a .sort(). For faster results, prefer array over list of object ptrs. \$\endgroup\$
    – J_H
    Dec 22, 2023 at 19:09
5
\$\begingroup\$

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.]

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm pretty sure log(log(n)) is impossible since that is below the time to do a single binary search \$\endgroup\$ Dec 23, 2023 at 23:41
  • 1
    \$\begingroup\$ +1! This answer is spot on! I have a small and very pedantic remark - it's not quite true that OP's merging takes O(n log n) time. Python's sort uses the popular TimSort algorithm, which on an input like this should detect the sorted runs and merge them in linear time. It's written in blazing fast C, which makes it faster than pretty much any other approach (in Python). See some rough timings here (timmerge means using .sort, heapmerge uses heapq.merge, and mymerge is the usual merge implementation). \$\endgroup\$ Dec 24, 2023 at 1:40
  • \$\begingroup\$ @OscarSmith Try an interpolation search. \$\endgroup\$
    – mdfst13
    Dec 24, 2023 at 14:08
  • \$\begingroup\$ interpolation search is not better without knowledge of the distribution of the data \$\endgroup\$ Dec 24, 2023 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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