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?
- 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?