My first solution using
def maximumProduct(self, nums): nums.sort() return max(nums[-1] * nums[-2] * nums[-3], nums * nums * nums[-1])
I found a exactly same solution in discuss. Anyway, O(NlogN) is not adorable and O(N) is possible.
def maximumProduct(self, nums): a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums) return max(a * a * a, b * b * a)
Make it 1 line if you like:
def maximumProduct(self, nums): return max(nums) * max(a * b for a, b in [heapq.nsmallest(2, nums), heapq.nlargest(3, nums)[1:]])
@lee215 I guess It should be O(N) in the title, not O(1). If you mean O(1) memory, then specify it additionally.
It is O(logN) for insert. In my case it takes O(1) to keep nlargest and O(N) to parse all numbers.
@lee215 Really? heap takes O(logN) in case of both push and pop. then how could nlargest be O(N)?
heap takes O(log3) = O(1) in case of both push and pop.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.