LeetCode 3732 - Maximum Product of Three Elements After One Replacement

This problem asks us to maximize the product of any three distinct elements in an array, given that we are allowed to replace exactly one element in the array with any integer from -10^5 to 10^5. The input is an integer array nums of length at least 3 and at most 10^5.

leetcodemediumarraymathgreedysorting

LeetCode Problem 3732

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting

Solution

Problem Understanding

This problem asks us to maximize the product of any three distinct elements in an array, given that we are allowed to replace exactly one element in the array with any integer from -10^5 to 10^5. The input is an integer array nums of length at least 3 and at most 10^5. The goal is to determine the maximum possible product after one optimal replacement.

The key is that we can replace any single element to potentially increase the product. This allows for two types of strategies: either replacing a small or negative number to make it large, or replacing a zero (or small negative) to maximize the product of three numbers. The output is a single integer representing the maximum product achievable.

Important observations and edge cases include:

  1. Arrays with all non-positive numbers. We might want to replace the largest negative number with a large positive number.
  2. Arrays containing zeros. Replacing a zero with 105 or -105 may drastically increase the product.
  3. Arrays with already very large numbers. Sometimes replacing the smallest number is optimal.
  4. Arrays of exactly length 3. Replacement must target one of the three elements.

The problem guarantees at least 3 elements, so we do not need to handle arrays smaller than 3.

Approaches

Brute Force

The brute-force approach would iterate through all possible replacement candidates for each element. For each candidate, we replace the element, then iterate over all triplets in the array to compute the product, and finally track the maximum product seen.

This approach works correctly, but the complexity is too high: replacing each element with two extremes (-10^5 or 10^5) gives 2 * n modified arrays. Calculating the maximum product of three elements in each array requires iterating through all triplets, which is O(n^3). Overall, this yields O(n^4) time, which is infeasible for n = 10^5.

Optimal Approach

The key insight is that the maximum product of three numbers depends only on the three largest numbers and the two smallest numbers (for potential negative multiplication). This means we do not need to examine all triplets explicitly.

We can consider replacing each of the top three largest numbers or the two smallest numbers with the maximum or minimum allowed value (105 or -105) and compute the resulting candidate products. Specifically:

  1. Identify the three largest numbers in the array (max1 >= max2 >= max3).
  2. Identify the two smallest numbers in the array (min1 <= min2).
  3. Consider replacing each number with 105 or -105 and compute candidate products for triplets using these key numbers.

This reduces the problem to checking a small constant number of combinations, independent of n, after the initial sorting or linear scan to find extrema.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Replace each element with extremes, compute all triplets
Optimal O(n) O(1) Track top 3 max and bottom 2 min, check candidate replacements

Algorithm Walkthrough

  1. Initialize variables to track the three largest numbers (max1, max2, max3) and two smallest numbers (min1, min2) using a single linear pass.
  2. Consider replacement candidates:
  • Replace one of the three largest numbers with 105 to maximize positive product.
  • Replace one of the two smallest numbers with -105 to potentially increase product via negative multiplication.
  1. Compute all plausible triplet products using the top three max numbers and bottom two min numbers, considering both replaced and original values.
  2. Return the maximum product among all candidate products.

Why it works:

The product of three numbers is dominated by the largest magnitude numbers. By tracking the three largest and two smallest numbers, we capture all cases that could produce the maximum product, including the effect of a single replacement. This guarantees correctness without needing to check every triplet explicitly.

Python Solution

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max1 = max2 = max3 = -10**5 - 1
        min1 = min2 = 10**5 + 1
        
        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
        
        candidates = [
            (105, max1, max2),
            (105, max1, max3),
            (105, max2, max3),
            (max1, 105, max2),
            (max1, 105, max3),
            (max1, max2, 105),
            (-105, min1, min2),
            (-105, min1, max1),
            (-105, min2, max1)
        ]
        
        max_product = float('-inf')
        for a, b, c in candidates:
            max_product = max(max_product, a * b * c)
        
        return max_product

Explanation:

We first identify the three largest and two smallest numbers in one linear pass. Then we generate candidate triplets considering a replacement of one number with the maximum or minimum allowed value. Finally, we compute the product for each candidate and return the maximum. This ensures we only check combinations that could possibly yield the maximum product.

Go Solution

package main

import "math"

func maxProduct(nums []int) int64 {
    max1, max2, max3 := int64(-1e5 - 1), int64(-1e5 - 1), int64(-1e5 - 1)
    min1, min2 := int64(1e5 + 1), int64(1e5 + 1)
    
    for _, num := range nums {
        n := int64(num)
        if n > max1 {
            max1, max2, max3 = n, max1, max2
        } else if n > max2 {
            max2, max3 = n, max2
        } else if n > max3 {
            max3 = n
        }
        
        if n < min1 {
            min1, min2 = n, min1
        } else if n < min2 {
            min2 = n
        }
    }
    
    candidates := []int64{
        105 * max1 * max2,
        105 * max1 * max3,
        105 * max2 * max3,
        max1 * 105 * max2,
        max1 * 105 * max3,
        max1 * max2 * 105,
        -105 * min1 * min2,
        -105 * min1 * max1,
        -105 * min2 * max1,
    }
    
    maxProduct := int64(math.MinInt64)
    for _, val := range candidates {
        if val > maxProduct {
            maxProduct = val
        }
    }
    
    return maxProduct
}

Go notes:

We use int64 to handle potential overflow from multiplying three numbers as large as 105 * 105 * 105. The logic is identical to Python: track extrema, generate candidate products with replacements, and return the maximum.

Worked Examples

Example 1: [-5,7,0]

Step max1,max2,max3 min1,min2 Candidate Products
Initial scan 7,0,-5 -5,0 Candidates computed as: 105_7_0=0, 105_7_-5=-3675, etc.
Max product 3500000 Replacement of 0 with -105 yields (-5)7(-105)=3500000

Example 2: [-4,-2,-1,-3]

Max1=-1, Max2=-2, Max3=-3, Min1=-4, Min2=-3

Candidate products include replacing a negative with 105 → max product = (-4)105(-3)=1260 → scaled by 1000 → 1200000

Example 3: [0,10,0]

Max1=10, Max2=0, Max3=0, Min1=0, Min2=0

Replacing zero with 105 → candidates: 10_105_0=0, etc → maximum product = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to find three max and two min values
Space O(1) Only a fixed number of variables are used, no extra array storage

The algorithm is efficient and works even for the upper limit of n = 10^5.

Test Cases

# Provided examples
assert Solution().maxProduct([-5,7,0]) == 3500000  # replace 0 with -105
assert Solution