Problem statement

https://leetcode.com/problems/maximum-product-of-three-numbers/

Solution

Note, that result is either three biggest numbers multiplied, or two smallest (which can be negative) multiplied by biggest. One way is to sort numbers and find answer in O(n log n). Another is to directly find 3 biggest and 2 smallest number in O(n).

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def maximumProduct(self, nums):
        A = [float('-inf'), float('-inf'), float('-inf')]
        B = [float('inf'), float('inf')]
        for num in nums:
            if   num >= A[0]: A = [num, A[0], A[1]]
            elif num >= A[1]: A = [A[0], num, A[1]]
            elif num >= A[2]: A = [A[0], A[1], num]
                
            if   num <= B[0]: B = [num, B[0]]
            elif num <= B[1]: B = [B[0], num]

        return max(A[0]*A[1]*A[2], A[0]*B[0]*B[1])