algoadvance

You are given an integer array nums, which is sorted in non-decreasing order. You need to find and return the maximum product of three numbers in nums.

Example 1:

Input: nums = [1,2,3]
Output: 6
Explanation: The product of the three values 1, 2 and 3 is 6.

Example 2:

Input: nums = [1,2,3,4]
Output: 24
Explanation: The product of the three values 2, 3 and 4 is 24.

Example 3:

Input: nums = [-1,-2,-3]
Output: -6
Explanation: The product of the three values -1, -2 and -3 is -6.

Clarifying Questions

  1. Input Constraints:
    • What is the range of values for integers in the nums list?
    • What is the length range of the nums list?
  2. Edge Cases:
    • What should be returned if the array has less than three numbers?

Strategy

The maximum product of three numbers in a sorted list can be derived from either:

  1. The product of the three largest numbers in the array.
  2. The product of the two smallest numbers (which can be negative) and the largest number.

Since the array is sorted, the three largest numbers will be the last three numbers in the array. For the smallest numbers, they will be the first two numbers in the array.

Hence, we need to consider:

Code

def maximumProduct(nums):
    # Since the array is sorted, the following indices hold:
    n = len(nums)
    
    # The three largest numbers
    a = nums[-1]
    b = nums[-2]
    c = nums[-3]
    
    # The two smallest numbers (which are in the first two positions) and the largest number
    d = nums[0]
    e = nums[1]
    
    # Compare the product of last three numbers with the product of first two and last one
    return max(a * b * c, d * e * a)

# Example usage
print(maximumProduct([1, 2, 3, 4]))  # Output: 24
print(maximumProduct([-1, -2, -3]))  # Output: -6

Time Complexity

The time complexity of this solution is O(1) because we are only accessing a few specific elements in the sorted array, and performing a constant number of arithmetic operations. The space complexity is also O(1) as we are not using any additional data structures that grow with input size.

Try our interview co-pilot at AlgoAdvance.com