# LeetCode 628: Maximum Product of Three Numbers

## Problem Restatement

We are given an integer array `nums`.

We need to choose three numbers from the array so that their product is as large as possible.

Return that maximum product.

The three numbers do not need to be next to each other. We only care about choosing any three different elements.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | The maximum product of any three numbers |
| Constraint | `nums.length >= 3` |

Example function shape:

```python
def maximumProduct(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3]
```

The only possible product is:

```python
1 * 2 * 3 = 6
```

So the answer is:

```python
6
```

Example 2:

```python
nums = [1, 2, 3, 4]
```

The best three numbers are `2`, `3`, and `4`.

```python
2 * 3 * 4 = 24
```

So the answer is:

```python
24
```

Example 3:

```python
nums = [-1, -2, -3]
```

There are exactly three numbers, so we must use all of them.

```python
-1 * -2 * -3 = -6
```

So the answer is:

```python
-6
```

## First Thought: Try Every Triple

The direct solution is to check every possible group of three numbers.

For every `i`, `j`, and `k`, where all indices are different, compute:

```python
nums[i] * nums[j] * nums[k]
```

Then keep the largest product.

Code:

```python
class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        n = len(nums)
        best = float("-inf")

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    best = max(best, nums[i] * nums[j] * nums[k])

        return best
```

This is correct, but it checks too many triples.

For `n` numbers, this takes `O(n^3)` time.

## Key Insight

The maximum product must come from one of two cases.

The first case is simple: use the three largest numbers.

```python
largest * second_largest * third_largest
```

This works when the best product comes from large positive values.

But negative numbers change the problem.

Two negative numbers multiply into a positive number. So the second possible answer is:

```python
largest * smallest * second_smallest
```

For example:

```python
nums = [-10, -10, 5, 2]
```

The three largest numbers are `-10`, `2`, and `5` if sorted carefully by value near the end we get:

```python
-10 * 2 * 5 = -100
```

But the two smallest numbers are `-10` and `-10`.

```python
-10 * -10 * 5 = 500
```

So the answer is `500`.

That means we only need five important values:

| Value | Why |
|---|---|
| Largest number | Used in both possible best products |
| Second largest number | Needed for three-largest case |
| Third largest number | Needed for three-largest case |
| Smallest number | May be a large negative |
| Second smallest number | May pair with the smallest negative |

## Algorithm: Sorting

Sort the array in ascending order.

After sorting:

| Expression | Meaning |
|---|---|
| `nums[-1]` | largest number |
| `nums[-2]` | second largest number |
| `nums[-3]` | third largest number |
| `nums[0]` | smallest number |
| `nums[1]` | second smallest number |

Then compute two candidate products:

```python
candidate1 = nums[-1] * nums[-2] * nums[-3]
candidate2 = nums[-1] * nums[0] * nums[1]
```

Return the larger one.

## Implementation

```python
class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        nums.sort()

        return max(
            nums[-1] * nums[-2] * nums[-3],
            nums[-1] * nums[0] * nums[1]
        )
```

## Code Explanation

First, we sort the array:

```python
nums.sort()
```

This puts the smallest values at the front and the largest values at the back.

The product of the three largest values is:

```python
nums[-1] * nums[-2] * nums[-3]
```

The product of the largest value and the two smallest values is:

```python
nums[-1] * nums[0] * nums[1]
```

This handles arrays with two large negative numbers.

Finally, we return the better of the two products:

```python
return max(...)
```

## Correctness

After sorting, `nums[-1]`, `nums[-2]`, and `nums[-3]` are the three largest values in the array.

If the maximum product uses three large positive numbers, then it is exactly:

```python
nums[-1] * nums[-2] * nums[-3]
```

If the maximum product uses negative numbers, it must use two negative numbers, because one negative number would make the product negative when multiplied by positive numbers. To make this product as large as possible, we want the two smallest numbers, since they are the most negative and give the largest positive product when multiplied together.

So that candidate is:

```python
nums[-1] * nums[0] * nums[1]
```

Any maximum product must be one of these two forms. The algorithm computes both and returns the larger value, so it returns the maximum possible product.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(1)` or `O(n)` | Depends on the sorting implementation |

The main idea is simple and reliable. Sorting gives direct access to the only values that can matter.

## Alternative Solution: One Pass

We can solve this without sorting.

Track the three largest numbers and the two smallest numbers while scanning the array once.

```python
class Solution:
    def maximumProduct(self, nums: list[int]) -> int:
        min1 = float("inf")
        min2 = float("inf")

        max1 = float("-inf")
        max2 = float("-inf")
        max3 = float("-inf")

        for num in nums:
            if num <= min1:
                min2 = min1
                min1 = num
            elif num <= min2:
                min2 = num

            if num >= max1:
                max3 = max2
                max2 = max1
                max1 = num
            elif num >= max2:
                max3 = max2
                max2 = num
            elif num >= max3:
                max3 = num

        return max(
            max1 * max2 * max3,
            max1 * min1 * min2
        )
```

This version has better asymptotic time complexity.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | One scan through the array |
| Space | `O(1)` | Only five variables are stored |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maximumProduct([1, 2, 3]) == 6
    assert s.maximumProduct([1, 2, 3, 4]) == 24
    assert s.maximumProduct([-1, -2, -3]) == -6
    assert s.maximumProduct([-10, -10, 5, 2]) == 500
    assert s.maximumProduct([-100, -2, -3, 1]) == 300
    assert s.maximumProduct([0, 0, 0]) == 0
    assert s.maximumProduct([-5, -4, -3, -2, -1]) == -6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]` | Minimum length |
| `[1, 2, 3, 4]` | Normal positive case |
| `[-1, -2, -3]` | All negative with exactly three values |
| `[-10, -10, 5, 2]` | Two negatives create the maximum |
| `[-100, -2, -3, 1]` | Smallest two values matter |
| `[0, 0, 0]` | Product can be zero |
| `[-5, -4, -3, -2, -1]` | All negative values |