2
\$\begingroup\$

The task is, you have an array of n numbers called nums, and an array of m numbers called maxes.

For each element in maxes, find the number of elements for which m is bigger than or equal to n.

nums = [4, 2, 5, 10, 8]
maxes = [3, 1, 7, 8]

output = [1, 0, 3, 4]

Eg, The first element, 3, in maxes, is only higher than 2 in nums, hence the first element in output is 1

The initial solution I could think of was trivial, and its O(n^2)

def sol_naive(nums,maxes):
    output = []
    for entry in maxes:
        higher_numbers = len([x for x in nums if x <= entry])
        output.append(higher_numbers)
    return output

Wondering if there's a better approach to solve this problem?

\$\endgroup\$
3
\$\begingroup\$

One simple observation is that this problem gets much easier if you sort nums O(n log(n). Then you can use bisect_left which uses binary search to find where an element would go in a sorted list and is O(log(n)) for each element in m. This yields a total time of O((n+m) log(n))

from bisect import bisect_left

def sol_sorted(nums,maxes):
    output = []
    nums.sort()
    for m in maxes:
        ind = bisect_left(nums, m)
        output.append(len(nums) - ind)
    return output
\$\endgroup\$
  • \$\begingroup\$ You might be able to do this slightly faster involving sorting maxes, but then you have to futz around a bunch with keeping output ordering, and id didn't seem worth it to me. \$\endgroup\$ – Oscar Smith Oct 19 '17 at 16:14
  • \$\begingroup\$ Very nice! thank you for making me a little smarter today \$\endgroup\$ – Wboy Oct 19 '17 at 16:47
  • \$\begingroup\$ If you sort maxes as well, you can get your time to O(n log(n) + m log(m)) , which benefits us the larger the length difference is between n & m. so if you want to do len(n) == 10000, len(m) == 10, it makes more sense to sort each once and then essentially use the combine step of merge-sort to find the indexes all in one go (at O(n + m)), as opposed to doing separate bisections for each max. \$\endgroup\$ – TemporalWolf Oct 19 '17 at 20:08
  • \$\begingroup\$ Yeah, that's what I was saying. The downside is that you have to keep track of the original order of maxes so output ends up in the right order. It's not algorithmically slower, but it requires more python, and adds a fair amount of overhead. I would be interested to see if it ever ends up faster in practice. \$\endgroup\$ – Oscar Smith Oct 19 '17 at 20:52
0
\$\begingroup\$

You could turn your for-loop into a list comprehension:

nums = [4, 2, 5, 10, 8]
maxes = [3, 1, 7, 8]
output = [len([x for x in nums if x <= entry]) for entry in maxes]
\$\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.