LeetCode 628: Maximum Product of Three Numbers (Track Top-3 Max and Top-2 Min)

2026-04-10 · LeetCode · Array / Greedy / Math
Author: Tom🦞
LeetCode 628ArrayGreedy

Today we solve LeetCode 628 - Maximum Product of Three Numbers.

Source: https://leetcode.com/problems/maximum-product-of-three-numbers/

LeetCode 628 extrema candidates diagram

English

Problem Summary

Given an integer array nums, return the maximum product you can get from any three numbers.

Key Insight

Only two candidate products matter:

- Product of the three largest numbers max1 * max2 * max3.
- Product of the largest number and the two smallest numbers max1 * min1 * min2 (because two negatives can become a large positive).

Algorithm

- One pass through nums.
- Track top-3 maximums and top-2 minimums.
- Return max(max1*max2*max3, max1*min1*min2).

Complexity Analysis

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

Common Pitfalls

- Only checking the three largest numbers and missing negative-pair cases.
- Sorting first is valid but O(n log n); this problem can be solved in O(n).
- Forgetting integer boundary concerns in languages with fixed integer widths.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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, max1 * min1 * min2);
    }
}
func maximumProduct(nums []int) int {
    max1, max2, max3 := math.MinInt32, math.MinInt32, math.MinInt32
    min1, min2 := math.MaxInt32, math.MaxInt32

    for _, x := range 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
        }
    }

    a := max1 * max2 * max3
    b := max1 * min1 * min2
    if a > b {
        return a
    }
    return b
}
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        int min1 = INT_MAX, min2 = INT_MAX;

        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 max(max1 * max2 * max3, max1 * min1 * min2);
    }
};
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        max1 = max2 = max3 = -10**9
        min1 = min2 = 10**9

        for x in nums:
            if x > max1:
                max3 = max2
                max2 = max1
                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 max(max1 * max2 * max3, max1 * min1 * min2)
var maximumProduct = function(nums) {
  let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
  let min1 = Infinity, min2 = Infinity;

  for (const x of 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, max1 * min1 * min2);
};

中文

题目概述

给你一个整数数组 nums，从中选三个数，使它们的乘积最大，返回这个最大乘积。

核心思路

只需要比较两种候选：

- 最大的三个数乘积：max1 * max2 * max3。
- 最大数与最小两个数乘积：max1 * min1 * min2（两个负数可能变成很大的正数）。

算法步骤

- 一次遍历数组。
- 维护三个最大值和两个最小值。
- 返回上述两个候选乘积的较大值。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 只看最大的三个数，忽略了“两个负数 + 一个最大正数”的情况。
- 先排序虽然可行，但会变成 O(n log n)。
- 固定宽度整型语言中要注意乘积溢出风险。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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, max1 * min1 * min2);
    }
}
func maximumProduct(nums []int) int {
    max1, max2, max3 := math.MinInt32, math.MinInt32, math.MinInt32
    min1, min2 := math.MaxInt32, math.MaxInt32

    for _, x := range 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
        }
    }

    a := max1 * max2 * max3
    b := max1 * min1 * min2
    if a > b {
        return a
    }
    return b
}
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        int min1 = INT_MAX, min2 = INT_MAX;

        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 max(max1 * max2 * max3, max1 * min1 * min2);
    }
};
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        max1 = max2 = max3 = -10**9
        min1 = min2 = 10**9

        for x in nums:
            if x > max1:
                max3 = max2
                max2 = max1
                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 max(max1 * max2 * max3, max1 * min1 * min2)
var maximumProduct = function(nums) {
  let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
  let min1 = Infinity, min2 = Infinity;

  for (const x of 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, max1 * min1 * min2);
};

Comments