LeetCode 628. Maximum Product of Three Numbers

Description

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

Given an integer array numsfind three numbers whose product is maximum and return the maximum product.

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

Input: nums = [1,2,3,4]
Output: 24

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints:

  • 3 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

Explanation

Sort the list. The maximum product could be the product of the first 3 numbers, or the product of the last 3 numbers, or the product of the first 2 numbers and the last number.

Python Solution

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        if len(nums) <= 3:
            product = 1
            
            for num in nums:
                product *= num
                
        
        nums = sorted(nums)
        
        return max(nums[0] * nums[1] * nums[2], nums[-3] * nums[-2] * nums[-1], nums[0] * nums[1] * nums[-1])
            
  • Time Complexity: O(Nlog(N)).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.