Stupid but fast Python Solution, beats 97.12 %


  • 0
    N

    Generally speaking, the time complexity is O(N), as we traverse through the whole list. The space complexity is not O(1), because slicing the list creates new copy. But we can avoid creating copy by using for n in itertools.islice(nums, 3, len(nums)):. I personally think traversing iterators might be slower than traversing list, but not quite sure.

    class Solution(object):
        def maximumProduct(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            temp = nums[:3]
            temp.sort()
            n1,n2,n3 = temp
            s2,s1 = temp[:2]
            for n in nums[3:]:
                if n > n3:
                    n3, n2, n1 = n, n3, n2
                elif n > n2:
                    n2, n1 = n, n2
                elif n > n1:
                    n1 = n
                
                if n < s2:
                    s2, s1 = n, s2
                elif n < s1:
                    s1 = n
            
            return max(n1 * n2 * n3, s1 * s2 * n3)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.