Maximum Product of Three Numbers

Problem Statement

In the given task, the objective is to identify a triplet within an array of integers, nums, such that the product of the three numbers is maximized. Once identified, the maximum product of these three numbers needs to be returned. This problem checks not only for the highest values but also accounts for the properties of multiplication involving negative numbers, where two negatives make a positive. Understanding both the array’s positive and negative bounds and considering edge scenarios like minimum and maximum possible array sizes are crucial for proper implementation.

Examples

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

Approach and Intuition

1. Analyze the problem with the provided examples which give an insight into potential scenarios:

   • In cases where all numbers are positive, the result is simply the product of the three largest numbers.
   • If the array consists of negatives, and since two negatives multiplied together give a positive, the product of two smallest (most negative) numbers and the largest positive number could potentially yield a higher product than three largest negatives.

2. Understand constraints:

   • The sequence's length varies from 3 to 10,000.
   • Elements range between -1000 and 1000, including both positives, negatives, and zero.

3. From the constraints and examples, several strategies emerge:

   • The array can be sorted first. Once sorted:
     • Evaluate the product of the top three numbers at the end of the list (largest values).
     • Evaluate the product of the last number (largest value) and the first two numbers in the list (smallest values which could be negatives).
   • Compare these two products and the larger of these will be the maximal product for the array.

This approach leverages the mathematical property that the product of two negative numbers is positive, along with the basic principle of sorting to streamline the selection of numbers to consider for the maximum product computation.

Solutions

public class Solution {
    public int highestProduct(int[] array) {
        int smallest = Integer.MAX_VALUE, secondSmallest = Integer.MAX_VALUE;
        int largest = Integer.MIN_VALUE, secondLargest = Integer.MIN_VALUE, thirdLargest = Integer.MIN_VALUE;
        for (int num: array) {
            if (num <= smallest) {
                secondSmallest = smallest;
                smallest = num;
            } else if (num <= secondSmallest) {
                secondSmallest = num;
            }
            if (num >= largest) {
                thirdLargest = secondLargest;
                secondLargest = largest;
                largest = num;
            } else if (num >= secondLargest) {
                thirdLargest = secondLargest;
                secondLargest = num;
            } else if (num >= thirdLargest) {
                thirdLargest = num;
            }
        }
        return Math.max(smallest * secondSmallest * largest, largest * secondLargest * thirdLargest);
    }
}