628. Maximum Product of Three Numbers

Array
Math
Sorting

TIME

O(n)

SPACE

O(1)

Intuition

If all numbers were non-negative, the answer would just be the three largest. But negatives flip the game: the product of the two most negative values is a large positive, which paired with the largest value can beat the top three. So exactly two candidates need comparing:

max1 * max2 * max3 (three largest)
min1 * min2 * max1 (two smallest × largest)

Every optimal triple falls into one of these two shapes.

Approach

In a single pass, track the three largest values (max1 >= max2 >= max3) and the two smallest (min1 <= min2).
Return max(max1 * max2 * max3, min1 * min2 * max1).

(Sorting and reading the ends works too, at O(n log n); the linear scan avoids the sort.)

Complexity

Time: O(n)
Space: O(1)

Edge Cases

All negative (Example 3) → three largest (least negative) win: -1 * -2 * -3 = -6
Mix of signs → two-negatives-times-max path may win (e.g. [-10,-10,1,3,2] → 300)
Product magnitude ≤ 1000³ = 10^9, fits in 32-bit int, but long in Java is harmless
Exactly three elements → both candidates coincide

Code

from typing import List


class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        """
        628. Maximum Product of Three Numbers
        Time: O(n)
        Space: O(1)
        """
        max1 = max2 = max3 = float("-inf")  # three largest
        min1 = min2 = float("inf")          # two smallest
        for x in nums:
            if x >= max1:
                max3, max2, max1 = max2, max1, x
            elif x >= max2:
                max3, max2 = max2, x
            elif x > max3:
                max3 = x
            if x <= min1:
                min2, min1 = min1, x
            elif x < min2:
                min2 = x
        return int(max(max1 * max2 * max3, min1 * min2 * max1))

/**
 * 628. Maximum Product of Three Numbers
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int x : nums) {
            if (x >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x >= max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
            if (x <= min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}