I wrote the below as a solution to:
Find the highest product of three numbers in a list
- 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?
- No, check for None input
- Can we assume this fits memory?
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?
- 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?