algorithm – Find the highest product of three numbers in a list (Python)

I wrote the below as a solution to:

Problem

Find the highest product of three numbers in a list

Constraints

  • Is the input a list of integers?
  • Can we get negative inputs?
  • Can there be duplicate entries in the input?
  • Will there always be at least three integers?
  • Can we assume the inputs are valid?
  • Can we assume this fits memory?

Solution

from functools import reduce
from typing import List, Set, Callable

class Solution(object):

    def max_prod_three(self, array: List(int)) -> int:
        if array is None:
            raise TypeError("array cannot be None")
        if len(array) < 3:
            raise ValueError("array must have at least 3 elements")
        pos: List(int) = (n for n in array if n >= 0)
        neg: List(int) = (n for n in array if n < 0)
        pos_len: int = len(pos)
        neg_len: int = len(neg)

        candidates: Set(int) = set()
        mult: Callable((int, int), int) = lambda x,y:x*y

        # possible combinations are:
        # ---, --+, -+-, +--, -++, +-+, ++-, +++
        # but order does not matter, so left with:
        # --- -> -  : len(neg) >= 3, will never be the max if len(pos) > = 3, if len(pos) < 3,
        #                            max will be with 3 lowest absolute values
        # --+ -> +  : len(neg) >= 2, len(pos) >= 1, will be the max if  exists -- > any ++
        # -++ -> -  : len(neg) >= 1, len(pos) >= 2, will never be the max if len(pos >= 3,
        #                            if len(pos) == 2, max will be with lowest absolute value
        # +++ -> +  : len(pos) >= 3, max is with 3 highest values

        if neg_len >= 3 and pos_len < 3:
            candidates.add(reduce(mult, sorted(neg)(-3:)))
        if neg_len >= 2 and pos_len >= 1:
            candidates.add(reduce(mult, sorted(neg)(:2) + (max(pos))))
        if neg_len >= 1 and pos_len == 2:
            candidates.add(reduce(mult, sorted(neg)(-1:) + pos))
        if pos_len >= 3:
            candidates.add(reduce(mult, sorted(pos)(-3:)))
        
        return max(candidates)

Please could I get some feedback on it? In particular:

  • Readability and does the comment make it clear what the code is doing?
  • Pythonic-ness
  • Typing – I have not really used typing before. Is using it on every variable worth doing, or overkill? If you know of a good resource to help a beginner, please add a link, thanks 🙂
  • Complexity – how would I calculate this in big-0 notation? The provided solution here is O(n) for time and O(1) space, but this runs much faster than that (~10x faster for list of 7,000 entries, ~2x faster for very small lists). Notice I loop over the array twice (to separate -ve and +ve numbers), while the solution given only loops over it once, but with quite a few min/max ops within that loop. As I understand it, my code is also O(n) (since O(2n) == O(n)). But if that is correct, how is the time taken so different?
  • Lastly, this is not written to be production code of course. But, what would/could I add to it for some hypothetical production use case?