Skip to content

628. Maximum Product of Three Numbers 👍

Approach 1: w/ sort

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
1
2
3
4
5
6
7
8
9
class Solution {
 public:
  int maximumProduct(vector<int>& nums) {
    const int n = nums.size();
    ranges::sort(nums);
    return max(nums[n - 1] * nums[0] * nums[1],
               nums[n - 1] * nums[n - 2] * nums[n - 3]);
  }
};

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

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

Approach 2: w/o sort

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  int maximumProduct(vector<int>& nums) {
    int min1 = INT_MAX;  // the minimum
    int min2 = INT_MAX;  // the second minimum
    int max1 = INT_MIN;  // the maximum
    int max2 = INT_MIN;  // the second maximum
    int max3 = INT_MIN;  // the third maximum

    for (const int num : nums) {
      if (num <= min1) {
        min2 = min1;
        min1 = num;
      } else if (num <= min2) {
        min2 = num;
      }
      if (num >= max1) {
        max3 = max2;
        max2 = max1;
        max1 = num;
      } else if (num >= max2) {
        max3 = max2;
        max2 = num;
      } else if (num >= max3) {
        max3 = num;
      }
    }

    return max(max1 * min1 * min2, max1 * max2 * max3);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int maximumProduct(int[] nums) {
    int min1 = Integer.MAX_VALUE; // the minimum
    int min2 = Integer.MAX_VALUE; // the second minimum
    int max1 = Integer.MIN_VALUE; // the maximum
    int max2 = Integer.MIN_VALUE; // the second maximum
    int max3 = Integer.MIN_VALUE; // the third maximum

    for (final int num : nums) {
      if (num <= min1) {
        min2 = min1;
        min1 = num;
      } else if (num <= min2) {
        min2 = num;
      }
      if (num >= max1) {
        max3 = max2;
        max2 = max1;
        max1 = num;
      } else if (num >= max2) {
        max3 = max2;
        max2 = num;
      } else if (num >= max3) {
        max3 = num;
      }
    }

    return max(max1 * min1 * min2, max1 * max2 * max3);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def maximumProduct(self, nums: list[int]) -> int:
    min1 = inf   # the minimum
    min2 = inf   # the second minimum
    max1 = -inf  # the maximum
    max2 = -inf  # the second maximum
    max3 = -inf  # the third maximum

    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 * min1 * min2, max1 * max2 * max3)