Solutions

1. Brute Force

O(n³) time | O(1) space

Intuition

We can try every combination of three elements and keep the largest product.

Algorithm

Create a largest integer variable with a minimal initial value.
Iterate through the outer loop from the first element to the last element with i index.
For each outer loop iteration, iterate through the middle loop from the element at i + 1 to the last element with j index.
For each middle loop iteration, iterate through the inner loop from the element at j + 1 to the last element with k index.
Keep the greater of largest and the product of the elements at i, j and k.
Return largest when all loops finish.

-10

-5

01234

i j k

3 * -10 * 4 = -120, largest = -120

1 / 11

Code

def maximumProduct(nums: list[int]) -> int:
    largest = float('-inf')
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
                largest = max(largest, nums[i] * nums[j] * nums[k])
    return largest

/**
 * @param {number[]} nums
 * @returns {number}
 */
var maximumProduct = function (nums) {
  let largest = -Infinity
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        largest = Math.max(largest, nums[i] * nums[j] * nums[k])
      }
    }
  }
  return largest
}

class Solution {
    public int maximumProduct(int[] nums) {
        int largest = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    largest = Math.max(largest, nums[i] * nums[j] * nums[k]);
                }
            }
        }
        return largest;
    }
}

2. Sorting

O(nlogn) time | O(1) space

Intuition

The greatest product is either the product of the three largest elements, or the product of the two smallest elements and the largest one, as two negative elements multiply into a positive number.

We can find those elements at both ends if we first sort the array.

Algorithm

Sort the array.
Multiply the last three elements.
Multiply the first two elements and the last element.
Return the greater of the two products.

-10

-5

01234

Sort the array

1 / 4

Code

def maximumProduct(nums: list[int]) -> int:
    nums.sort()
    return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

/**
 * @param {number[]} nums
 * @returns {number}
 */
var maximumProduct = function (nums) {
  nums.sort((a, b) => a - b)
  const n = nums.length
  return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1])
}

import java.util.Arrays;

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
    }
}

3. One Pass

O(n) time | O(1) space

Intuition

The greatest product is either the product of the three largest elements, or the product of the two smallest elements and the largest one, as two negative elements multiply into a positive number.

We can find those elements with one iteration over the whole array.

Algorithm

Create max1, max2 and max3 variables for the three largest elements, and min1 and min2 for the two smallest elements.
Iterate through the array.
- If the element is greater than max1, put the element into max1, update max2 with the old max1 value and update max3 with the old max2 value.
- Otherwise, if it is greater than max2, put the element into max2 and update max3 with the old max2 value.
- Otherwise, if it is greater than max3, put the element into max3.
- In the same way, update min1 and min2 values.
Return the greater of max1 * max2 * max3 and min1 * min2 * max1.

-10

-5

01234

max1 = 3, min1 = 3

1 / 7

Code

def maximumProduct(nums: list[int]) -> int:
    max1 = max2 = max3 = float('-inf')
    min1 = min2 = float('inf')
    for num in nums:
        if num > max1:
            max1, max2, max3 = num, max1, max2
        elif num > max2:
            max2, max3 = num, max2
        elif num > max3:
            max3 = num
        if num < min1:
            min1, min2 = num, min1
        elif num < min2:
            min2 = num
    return max(max1 * max2 * max3, min1 * min2 * max1)

/**
 * @param {number[]} nums
 * @returns {number}
 */
var maximumProduct = function (nums) {
  let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity
  let min1 = Infinity, min2 = Infinity
  for (const num of nums) {
    if (num > max1) {
      [max1, max2, max3] = [num, max1, max2]
    } else if (num > max2) {
      [max2, max3] = [num, max2]
    } else if (num > max3) {
      max3 = num
    }
    if (num < min1) {
      [min1, min2] = [num, min1]
    } else if (num < min2) {
      min2 = num
    }
  }
  return Math.max(max1 * max2 * max3, min1 * min2 * max1)
}

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 num : nums) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}