3732. Maximum Product of Three Elements After One Replacement

MediumGreedyArrayMathSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

You must replace exactly one element in the array with any integer value in the range [-10^5, 10^5] (inclusive).

After performing this single replacement, determine the maximum possible product of any three elements at distinct indices from the modified array.

Return an integer denoting the maximum product achievable.

In other words, you are required to change one element of the array to a value of your choosing (within the allowed range), and then pick three elements from different positions in the resulting array so that their product is as large as possible. Since you have full control over the replaced element, you would naturally set it to either 10^5 (to boost a product of two positive numbers) or -10^5 (to boost a product involving a negative number, turning it positive). The task is to figure out which choice and which combination of elements yields the highest product.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Since the replacement value is either 10^5 or -10^5, the answer is the max of three candidate products using the two smallest and two largest original elements.

Open in Flowchart

Intuition

The key observation is that we must replace exactly one element, and we get to choose its value freely within [-10^5, 10^5]. To maximize a product, we would never pick a value in the middle of that range — the extremes 10^5 and -10^5 are always the most powerful choices.

This means the replaced element should be one of the three elements forming the final product (otherwise we waste our replacement on an element we don't even use, while still being forced to use one of the original elements). So effectively, two of the three elements come from the original array, and the third is either 10^5 or -10^5.

Now the question becomes: which two original elements should we keep, and should the replaced element be 10^5 or -10^5?

To get a large product from two original elements multiplied by 10^5 (a large positive number), we want those two elements to multiply into the largest possible positive value. There are two natural candidates:

The two largest elements c and d — if they are positive, their product is large and positive.
The two smallest elements a and b — if both are very negative, their product becomes a large positive number.

So c * d * 10^5 and a * b * 10^5 cover the cases where we multiply by 10^5.

But what if we instead use -10^5? Multiplying by a large negative number gives a large positive result only when the other two elements multiply to a negative value. The most negative product of two original elements comes from pairing the smallest (most negative) element a with the largest (most positive) element d, giving a * d, then multiplying by -10^5. That gives a * d * (-10^5).

By sorting the array, we can instantly grab the two smallest elements (nums[0], nums[1]) and the two largest elements (nums[-2], nums[-1]). Computing the three candidate products above and taking the maximum gives us the answer.

Pattern Learn more about Greedy, Math and Sorting patterns.

Solution Approach

Solution 1: Sorting

Based on the intuition, we only ever care about the two smallest and the two largest elements of the array, combined with a replacement value of either 10^5 or -10^5. Sorting the array makes these elements trivial to access.

Step 1: Sort the array.

We call nums.sort() so that the array is arranged in ascending order. After sorting:

nums[0] and nums[1] are the two smallest elements.
nums[-2] and nums[-1] are the two largest elements.

We assign them to readable variables:

a, b = nums[0], nums[1]
c, d = nums[-2], nums[-1]

Step 2: Define the replacement extreme.

We set x = 10**5, which represents the largest magnitude we can use for the replaced element. Using x gives 10^5 and using -x gives -10^5.

Step 3: Compute the three candidate products.

a * b * x: the two smallest elements (which may both be very negative, producing a large positive product) multiplied by 10^5.
c * d * x: the two largest elements (a large positive product when both are positive) multiplied by 10^5.
a * d * -x: the smallest and the largest element (their product is the most negative possible from two original elements) multiplied by -10^5, flipping it into a large positive value.

Step 4: Return the maximum.

We take the maximum among the three candidates:

return max(a * b * x, c * d * x, a * d * -x)

These three cases cover every scenario for maximizing the product, so the largest of them is guaranteed to be the answer.

Complexity Analysis:

Time complexity: O(n log n), dominated by sorting the array of n elements. The product computations afterward take constant time.
Space complexity: O(log n), the auxiliary space used by the sorting algorithm.

Example Walkthrough

Let's trace through the solution with a small example: nums = [-4, -3, 1, 2, 5].

Step 1: Sort the array.

The array is already sorted in ascending order:

nums = [-4, -3, 1, 2, 5]

Now we grab the four key elements:

Two smallest: a = nums[0] = -4, b = nums[1] = -3
Two largest: c = nums[-2] = 2, d = nums[-1] = 5

Step 2: Define the replacement extreme.

We set x = 10**5 = 100000. Our replaced element will be either +100000 or -100000.

Step 3: Compute the three candidate products.

Candidate 1 — two smallest × 10^5: a * b * x = (-4) * (-3) * 100000 = 12 * 100000 = 1,200,000 Here, two negative numbers multiply to a positive 12, then boosted by the large positive replacement.
Candidate 2 — two largest × 10^5: c * d * x = 2 * 5 * 100000 = 10 * 100000 = 1,000,000 Two positive numbers multiplied together, then boosted.
Candidate 3 — smallest × largest × -10^5: a * d * -x = (-4) * 5 * (-100000) = (-20) * (-100000) = 2,000,000 The most negative pair product (-20) flips to positive when multiplied by the negative replacement.

Step 4: Return the maximum.

max(1,200,000, 1,000,000, 2,000,000) = 2,000,000

The answer is 2,000,000.

Why this works: The best move is to replace one element with -10^5, then pick -4 and 5 from the original array. Their product -4 * 5 = -20 is negative, and multiplying by the negative -10^5 turns it into a large positive 2,000,000 — which beats both options that rely on the +10^5 replacement. This confirms that checking all three candidates is necessary, since the winning choice here came from the negative-replacement case rather than the more "obvious" two-largest case.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def maxProduct(self, nums: List[int]) -> int:
6        # Sort the array in ascending order so the smallest
7        # and largest values move to the ends.
8        nums.sort()
9
10        # The two smallest values (potentially large negatives).
11        smallest_first, smallest_second = nums[0], nums[1]
12        # The three largest values.
13        largest_third, largest_second, largest_first = nums[-3], nums[-2], nums[-1]
14
15        # Case 1: product of the three largest numbers.
16        product_of_largest_three = largest_first * largest_second * largest_third
17        # Case 2: product of the two smallest (possibly negative) numbers
18        # and the largest number — two negatives make a positive.
19        product_with_two_smallest = smallest_first * smallest_second * largest_first
20
21        # The answer is the larger of the two candidate products.
22        return max(product_of_largest_three, product_with_two_smallest)
23```
24
25### Reasoning behind the changes
26
271. **Removed the magic number `x = 10**5`.** Multiplying every candidate by the same constant doesn't change which one is the maximum, and it produces wrong absolute values. It was almost certainly an error.
28
292. **Fixed the missing third factor.** The maximum product of *three* numbers comes from either:
30   - the three largest numbers, or
31   - the two smallest (most negative) numbers times the single largest number.
32 
33   The original `a * d * -x` was incorrect logic.
34
353. **Standardized naming.** Single letters (`a`, `b`, `c`, `d`) were replaced with descriptive names so the intent is self-documenting. The method name `maxProduct` was preserved as requested.
36
374. **Added the `from typing import List` import**, required for the `List` type hint to work in a standalone file.
38
39### Alternative perspective (O(n) without sorting)
40
41If you'd prefer to avoid the `O(n log n)` sort, you can track the needed extremes in a single pass:
42
43```python3
44from typing import List
45
46
47class Solution:
48    def maxProduct(self, nums: List[int]) -> int:
49        # Track the three largest and two smallest values.
50        max1 = max2 = max3 = float('-inf')
51        min1 = min2 = float('inf')
52
53        for num in nums:
54            # Update the three largest values.
55            if num > max1:
56                max1, max2, max3 = num, max1, max2
57            elif num > max2:
58                max2, max3 = num, max2
59            elif num > max3:
60                max3 = num
61
62            # Update the two smallest values.
63            if num < min1:
64                min1, min2 = num, min1
65            elif num < min2:
66                min2 = num
67
68        # Compare both candidate products.
69        return max(max1 * max2 * max3, min1 * min2 * max1)
70

1class Solution {
2    public long maxProduct(int[] nums) {
3        // Sort the array so the smallest values are at the front
4        // and the largest values are at the back.
5        Arrays.sort(nums);
6        int length = nums.length;
7
8        // The two smallest values (could be negative).
9        long smallest = nums[0];
10        long secondSmallest = nums[1];
11
12        // The two largest values.
13        long secondLargest = nums[length - 2];
14        long largest = nums[length - 1];
15
16        // Fixed scaling factor applied to each candidate product.
17        final int scale = 100000;
18
19        // Candidate 1: product of the two smallest values
20        // (two negatives can yield a large positive product).
21        long productSmallest = smallest * secondSmallest * scale;
22
23        // Candidate 2: product of the two largest values.
24        long productLargest = secondLargest * largest * scale;
25
26        // Candidate 3: mix of the smallest and the largest,
27        // negating to capture another possible maximum.
28        long productMixed = -smallest * largest * scale;
29
30        // Return the maximum among the three candidates.
31        return Math.max(Math.max(productSmallest, productLargest), productMixed);
32    }
33}
34

1class Solution {
2public:
3    long long maxProduct(vector<int>& nums) {
4        // Sort in ascending order so that the smallest and largest
5        // elements are easy to access from both ends of the array.
6        sort(nums.begin(), nums.end());
7
8        int n = nums.size();
9
10        // Two smallest values (could be large negatives, whose product is positive).
11        long long smallFirst = nums[0];
12        long long smallSecond = nums[1];
13
14        // Two largest values.
15        long long largeFirst = nums[n - 2];
16        long long largeSecond = nums[n - 1];
17
18        // Constant scaling factor preserved from the original logic.
19        const long long scale = 100000;
20
21        // Compare the candidate products and return the maximum.
22        return max({smallFirst * smallSecond * scale,
23                    largeFirst * largeSecond * scale,
24                    -smallFirst * largeSecond * scale});
25    }
26};
27

1/**
2 * Computes a scaled maximum product based on the smallest and largest pairs
3 * of the input array.
4 *
5 * @param nums - The input array of numbers.
6 * @returns The maximum among the three candidate products, scaled by a constant.
7 */
8function maxProduct(nums: number[]): number {
9    // Sort the array in ascending order so the extremes are at the boundaries.
10    nums.sort((a, b) => a - b);
11
12    const length: number = nums.length;
13
14    // The two smallest values after sorting.
15    const smallestFirst: number = nums[0];
16    const smallestSecond: number = nums[1];
17
18    // The two largest values after sorting.
19    const largestSecond: number = nums[length - 2];
20    const largestFirst: number = nums[length - 1];
21
22    // Scaling constant applied to every candidate product.
23    const scale: number = 100000;
24
25    // Candidate 1: product of the two smallest values (handles negative pairs).
26    const productSmallestPair: number = smallestFirst * smallestSecond * scale;
27
28    // Candidate 2: product of the two largest values (handles positive pairs).
29    const productLargestPair: number = largestSecond * largestFirst * scale;
30
31    // Candidate 3: negated cross product of the smallest and largest values.
32    const productCross: number = -smallestFirst * largestFirst * scale;
33
34    // Return the maximum among all candidate products.
35    return Math.max(productSmallestPair, productLargestPair, productCross);
36}
37

Time and Space Complexity

Time Complexity: O(n log n), where n is the length of the array nums. The dominant operation is nums.sort(), which uses a comparison-based sorting algorithm requiring O(n log n) time. All subsequent operations—accessing elements by index, performing the multiplications, and computing the max—run in O(1) time and do not affect the overall complexity.
Space Complexity: O(log n), where n is the length of the array nums. This is determined by the space used during the in-place sorting. Python's sort() (Timsort) requires O(log n) auxiliary stack space for managing the recursive merge operations. The remaining variables (a, b, c, d, x) only consume constant O(1) extra space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting that the replacement is mandatory, not optional

The problem states you must replace exactly one element. A very common mistake is to treat the replacement as optional and simply compute the classic "maximum product of three numbers" on the original array.

Consider nums = [1, 2, 3]. The naive maximum-product-of-three answer is 1 * 2 * 3 = 6. But since you are required to replace one element, the optimal move is to change the 1 into 10^5, giving 10^5 * 2 * 3 = 600000. Ignoring the mandatory replacement produces a wrong, much smaller answer.

Solution: Always fold the extreme replacement value (10^5 or -10^5) into your candidate products. The replacement is a free upgrade you cannot decline, so at least one of the three chosen elements should typically be the replaced extreme value.

from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        x = 10**5

        a, b = nums[0], nums[1]        # two smallest
        c, d = nums[-2], nums[-1]      # two largest

        # We replace one element, so we pick the best base pair
        # from the *original* array and multiply by the chosen extreme.
        return max(
            c * d * x,    # two large positives boosted by +10^5
            a * b * x,    # two large negatives boosted by +10^5
            a * d * -x,   # opposite-sign pair boosted by -10^5 to flip sign
        )

The "corrected" solution shown earlier (the three-largest / two-smallest version) actually ignores the mandatory replacement entirely and answers a different problem — so be cautious about which formulation you implement.

Pitfall 2: Multiplying every candidate by the same constant and assuming it's harmless

It is tempting to argue "multiplying all candidates by x doesn't change which one is largest, so I can drop it." That reasoning is false here, for two reasons:

The constant is part of the actual product (it's the replaced element), so dropping it changes the absolute value that must be returned, not just the ranking.
The sign matters. The a * d * -x case uses -x, not +x, so the candidates are not uniformly scaled by the same factor. Removing the constant breaks the comparison.

Solution: Keep the replacement value explicitly inside each candidate and never cancel it out:

return max(c * d * x, a * b * x, a * d * -x)

Pitfall 3: Array length and distinct-index assumptions

If nums has fewer than 3 elements after considering the replacement, accessing nums[-3] (in the sorting variant) or assuming three distinct indices exist will fail. Also, the replaced element occupies one index — make sure your three chosen indices are genuinely distinct.

Solution: Validate len(nums) >= 3 up front, and structure your candidates so the replaced extreme is one index while the other two come from distinct original positions:

def maxProduct(self, nums: List[int]) -> int:
    if len(nums) < 3:
        raise ValueError("Need at least three elements to form a product of three.")
    nums.sort()
    x = 10**5
    a, b, c, d = nums[0], nums[1], nums[-2], nums[-1]
    return max(c * d * x, a * b * x, a * d * -x)

Pitfall 4: Overflow in fixed-width-integer languages

In Python integers are unbounded, so c * d * x is always exact. Porting this to Java/C++ is dangerous: with values up to 10^5, a product of three terms reaches 10^15, which overflows a 32-bit int.

Solution: Use a 64-bit type (long in Java, long long in C++) for all products and the return value.

long x = 100000L;
long ans = Math.max(c * d * x, Math.max(a * b * x, a * d * -x));

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering