628-Maximum Product of Three Numbers-Py All-in-One By Talse
Get it Done, Make it Better, Share the Best -- Talse\nI). Naive Sort\n| O(T): O(nlgn) | O(S): O(1) | Rt: 284ms | \npython\n    def maximumProduct(self, nums: Li
**Get it Done, Make it Better, Share the Best -- Talse**\n**I). Naive Sort**\n| O(T): O(nlgn) | O(S): O(1) | Rt: 284ms | \n```python\n    def maximumProduct(self, nums: List[int]) -> int:\n        nums.sort()\n        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])\n```\n\n\n**II). Limit State**\n| O(T): O(n) | O(S): O(1) | Rt: 284ms | \n```python\n    def maximumProduct(self, nums: List[int]) -> int:\n        max1 = max2 = max3 = -float(\'inf\')\n        min1 = min2 = float(\'inf\')\n        for i in nums:\n            if i > max1: max1, max2, max3 = i, max1, max2\n            elif i > max2: max2, max3 = i, max2\n            elif i > max3: max3 = i\n            if i < min1: min1, min2 = i, min1\n            elif i < min2: min2 = i\n        return max(min1 * min2 * max1, max1 * max2 * max3)\n```\n\n\n**III). Combination**\n| O(T): O(nlgn) | O(S): O(1) | Rt: 276ms | \n```python\n    def maximumProduct(self, nums: List[int]) -> int:\n        nums.sort()\n        del nums[2:-3]\n        return max(a * b * c for a, b, c in itertools.combinations(nums, 3))\n```\nReferrence: https://leetcode.com/problems/maximum-product-of-three-numbers/discuss/104779/Python-Straightforward-with-Explanation\n\n\n**IV). Min Heap**\n| O(T): O(nlgn) | O(S): O(1) | Rt: 372ms | \n```python\n    def maximumProduct(self, nums: List[int]) -> int:\n        ncopy = copy.deepcopy(nums)\n        heapq.heapify(ncopy)\n        min1, min2 = heapq.heappop(ncopy), heapq.heappop(ncopy)\n        \n        neg = [-i for i in nums]\n        heapq.heapify(neg)\n        max1, max2, max3 = -heapq.heappop(neg), -heapq.heappop(neg), -heapq.heappop(neg)\n        \n        return max(min1 * min2 * max1, max1 * max2 * max3) \n```\nComment: this heap solution heapify all nums therefore is of time complexity O(nlgn). In real case, we don\'t need to heapify all elements. The refined version is provided as follows.\nAlternative: heapq nlargest and nsmallest. | O(T): O(nlgk) | O(S): O(1) | Rt: 276ms | \n```python\n    def maximumProduct(self, nums: List[int]) -> int:\n        hpl, hps = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)\n        return max(hpl[0] * hpl[1] * hpl[2], hps[-1] * hps[-2] * hpl[0])\n```\nReferrence: https://leetcode.com/problems/maximum-product-of-three-numbers/discuss/104739/Python-O(N)-and-1-line\nComment: heap solution is compatible for maximum product of k numbers. \n\n
[]