Python concise solution, O(N) and 1 line


  • 12

    My first solution using sort

    def maximumProduct(self, nums):
            nums.sort()
            return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * 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[0] * a[1] * a[2], b[0] * b[1] * a[0])
    

    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:]])

  • 0
    A

    @lee215 I guess It should be O(N) in the title, not O(1). If you mean O(1) memory, then specify it additionally.


  • 0
    D
    This post is deleted!

  • 0
    M

    heapq seems "logN" when getting nsmallest and nlargest.
    Am I wrong?


  • 1

    @motal
    It is O(logN) for insert. In my case it takes O(1) to keep nlargest and O(N) to parse all numbers.


  • 0
    M

    @lee215 Really? heap takes O(logN) in case of both push and pop. then how could nlargest be O(N)?


  • 2

    @motal
    heap takes O(log3) = O(1) in case of both push and pop.


  • 0
    N

    Loved your heap implementation. One optimisation that can be done is rather than two loops for finding the nlargest and the nsmallest, we can do it in one loop but the code wont look so clean.


Log in to reply
 

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