[Python] O(N) and 1 line
My first solution using sort\n\ndef maximumProduct(self, nums):\n        nums.sort()\n        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * num
My first solution using ```sort```\n````\ndef maximumProduct(self, nums):\n        nums.sort()\n        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])\n`````\nI found a exactly same solution in discuss. Anyway, O(NlogN) is not adorable and O(N) is possible.\n````\ndef maximumProduct(self, nums):\n        a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)\n        return max(a[0] * a[1] * a[2], b[0] * b[1] * a[0])\n`````\nMake it 1 line if you like:\n````\n    def maximumProduct(self, nums):\n        return max(nums) * max(a * b for a, b in [heapq.nsmallest(2, nums), heapq.nlargest(3, nums)[1:]])\n````\n\n**Update:**\n**Q:** Time complexity?\n**A:** Let me make it clear.\nMy solution is `O(NlogK)`, where K = 3.\nSo I said it\'s `O(N)`\nAnd the best solution can be `O(N)`.\n\n\n@macheret help explained the following:\n\nFor heapq.nlargest / heapq.nsmallest, looking at the (source code)[https://github.com/python/cpython/blob/e22072fb11246f125aa9ff7629c832b9e2407ef0/Lib/heapq.py#L545-L559]\n\nFirst, k items are heapified - that\'s an O(k*log(k)) operation.\nThen, n-k items are added into the heap with heapreplace - that\'s n-k O(log(k)) operations, or O((n-k)*log(k)).\nAdd those up, you get O(n*log(k)).\nIn this case k is constant and doesn\'t scale with n, so this usage is O(n).
[]