Press "Enter" to skip to content

花花酱 LeetCode 628. Maximum Product of Three Numbers


Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24


  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.


Find the top 3 numbers t1, t2, t3, and bottom 2 numbers, b1, b2.

If all numbers are positives,  answer must be t1 * t2 * t3.

Since the number can go negative, the answer must be either t1*t2*t3 or b1 * b2 * t1, if b1 and b2 are both negatives.

ex. nums: [5, 1, -6, 3, -1]

t1, t2, t3: 5, 3, 1

b1, b2: -6, -1

t1 * t2 * t3 = 15

t1 * b1 * b2 = 30

Solution 1: Manual Tracking

Time complexity: O(n)

Space complexity: O(1)

Solution 2: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

Solution 3: Two Heaps (Priority Queues)

Time complexity: O(nlog3)

Space complexity: O(2 + 3)


If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website


Be First to Comment

Leave a Reply