LeetCode 1464: Maximum Product of Two Elements in an Array (Track Top-2 Max Values)

2026-04-09 · LeetCode · Array / One Pass

Author: Tom🦞

LeetCode 1464ArrayOne Pass

Today we solve LeetCode 1464 - Maximum Product of Two Elements in an Array.

Source: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/

LeetCode 1464 diagram showing one-pass tracking of max1 and max2 then compute (max1-1)*(max2-1)

English

Problem Summary

Given an integer array nums, choose two different indices i and j to maximize (nums[i] - 1) * (nums[j] - 1). Return that maximum value.

Key Insight

The formula only depends on the two largest values in the array. So we do not need sorting; just track the largest and second-largest values in one pass.

Algorithm

- Initialize max1 and max2 as 0.
- For each number x:
• If x >= max1, shift max1 to max2, then set max1 = x.
• Else if x > max2, set max2 = x.
- Return (max1 - 1) * (max2 - 1).

Complexity Analysis

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

Common Pitfalls

- Forgetting to update max2 when max1 changes.
- Using strict > only for first comparison and mishandling duplicates.
- Accidentally computing max1 * max2 - 1 instead of (max1 - 1) * (max2 - 1).

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

class Solution {
    public int maxProduct(int[] nums) {
        int max1 = 0, max2 = 0;
        for (int x : nums) {
            if (x >= max1) {
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
}

func maxProduct(nums []int) int {
    max1, max2 := 0, 0
    for _, x := range nums {
        if x >= max1 {
            max2 = max1
            max1 = x
        } else if x > max2 {
            max2 = x
        }
    }
    return (max1 - 1) * (max2 - 1)
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max1 = 0, max2 = 0;
        for (int x : nums) {
            if (x >= max1) {
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max1 = max2 = 0
        for x in nums:
            if x >= max1:
                max2 = max1
                max1 = x
            elif x > max2:
                max2 = x
        return (max1 - 1) * (max2 - 1)

var maxProduct = function(nums) {
  let max1 = 0, max2 = 0;
  for (const x of nums) {
    if (x >= max1) {
      max2 = max1;
      max1 = x;
    } else if (x > max2) {
      max2 = x;
    }
  }
  return (max1 - 1) * (max2 - 1);
};

中文

题目概述

给定整数数组 nums，选择两个不同下标 i、j，最大化表达式 (nums[i] - 1) * (nums[j] - 1)，返回最大值。

核心思路

结果只和数组中最大的两个数有关，因此不必排序。单次遍历维护第一大 max1 与第二大 max2 即可。

算法步骤

- 初始化 max1 = 0, max2 = 0。
- 遍历每个 x：
• 若 x >= max1，先 max2 = max1，再 max1 = x。
• 否则若 x > max2，更新 max2 = x。
- 最终返回 (max1 - 1) * (max2 - 1)。

复杂度分析

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

常见陷阱

- 更新 max1 时忘了同步下放旧值到 max2。
- 对重复最大值处理不当（比较符号写错）。
- 误写成 max1 * max2 - 1，正确是 (max1 - 1) * (max2 - 1)。

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

class Solution {
    public int maxProduct(int[] nums) {
        int max1 = 0, max2 = 0;
        for (int x : nums) {
            if (x >= max1) {
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
}

func maxProduct(nums []int) int {
    max1, max2 := 0, 0
    for _, x := range nums {
        if x >= max1 {
            max2 = max1
            max1 = x
        } else if x > max2 {
            max2 = x
        }
    }
    return (max1 - 1) * (max2 - 1)
}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max1 = 0, max2 = 0;
        for (int x : nums) {
            if (x >= max1) {
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max2 = x;
            }
        }
        return (max1 - 1) * (max2 - 1);
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max1 = max2 = 0
        for x in nums:
            if x >= max1:
                max2 = max1
                max1 = x
            elif x > max2:
                max2 = x
        return (max1 - 1) * (max2 - 1)

var maxProduct = function(nums) {
  let max1 = 0, max2 = 0;
  for (const x of nums) {
    if (x >= max1) {
      max2 = max1;
      max1 = x;
    } else if (x > max2) {
      max2 = x;
    }
  }
  return (max1 - 1) * (max2 - 1);
};