Maximum Product of Three Numbers Interview Question for Meta

## Maximum Product of Three Numbers

### Problem Description

Given an integer array `nums`, the task is to find 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


### Naive Solution

A straightforward approach would be to generate all possible combinations of three numbers from the array, calculate their product, and then find the maximum among these products. This involves three nested loops, resulting in a time complexity of O(n^3).

```python
import sys

def maximum_product_naive(nums):
    n = len(nums)
    if n < 3:
        return None  # Or raise an exception

    max_product = -sys.maxsize - 1
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                product = nums[i] * nums[j] * nums[k]
                max_product = max(max_product, product)
    return max_product

Optimal Solution

A more efficient approach is to sort the array and then consider two cases:

The product of the three largest numbers.
The product of the two smallest (most negative) numbers and the largest number.

The maximum of these two products will be the answer. This method has a time complexity of O(n log n) due to the sorting step.

def maximum_product(nums):
    nums.sort()
    n = len(nums)
    return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1])

Big(O) Run-time Analysis

The optimal solution involves sorting the array, which typically uses an algorithm like quicksort or mergesort with an average time complexity of O(n log n). After sorting, we perform a constant number of multiplications and comparisons, which take O(1) time.

Therefore, the overall time complexity is dominated by the sorting step, making it O(n log n).

Big(O) Space Usage Analysis

The space complexity depends on the sorting algorithm used.

If the sorting is done in-place (e.g., using heapsort), the space complexity is O(1), as we only use a constant amount of extra space.
If the sorting algorithm requires additional space (e.g., mergesort), the space complexity could be O(n) in the worst case.

In the provided Python code, nums.sort() is generally implemented using Timsort, which has a space complexity that can range from O(1) to O(n) depending on the input array's characteristics. For simplicity, we can assume O(log n) space complexity in most practical scenarios.

Edge Cases

Array with fewer than three elements:
- If the array has fewer than three elements, it's impossible to find three numbers to multiply. You should either return an error or a specific value (e.g., None).
Array with all positive numbers:
- The maximum product will always be the product of the three largest numbers.
Array with all negative numbers:
- The maximum product will be the product of the three largest (least negative) numbers.
Array with a mix of positive and negative numbers:
- This is where the second case in the optimal solution becomes important. The two smallest (most negative) numbers multiplied together can result in a large positive number. The maximum product is either the product of the three largest positive numbers or the product of the two smallest negative numbers and the largest positive number.
Zeroes in the array:
- If the array contains zero, and the maximum product is positive, multiplying by zero will always result in a smaller product. Zeroes should be considered when determining the maximum product.

Here's how the optimal solution handles these cases:

Sorting allows easy access to the smallest and largest elements.
Comparing the two potential maximum products handles the mix of positive and negative numbers correctly.

def maximum_product_with_edge_cases(nums):
    n = len(nums)
    if n < 3:
        raise ValueError("Array must have at least three elements")

    nums.sort()
    return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1])