Skip to content

3732. Maximum Product of Three Elements After One Replacement

Description

You are given an integer array nums.

You must replace exactly one element in the array with any integer value in the range [-105, 105] (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.

 

Example 1:

Input: nums = [-5,7,0]

Output: 3500000

Explanation:

Replacing 0 with -105 gives the array [-5, 7, -105], which has a product (-5) * 7 * (-105) = 3500000. The maximum product is 3500000.

Example 2:

Input: nums = [-4,-2,-1,-3]

Output: 1200000

Explanation:

Two ways to achieve the maximum product include:

  • [-4, -2, -3] → replace -2 with 105 → product = (-4) * 105 * (-3) = 1200000.
  • [-4, -1, -3] → replace -1 with 105 → product = (-4) * 105 * (-3) = 1200000.
The maximum product is 1200000.

Example 3:

Input: nums = [0,10,0]

Output: 0

Explanation:

There is no way to replace an element with another integer and not have a 0 in the array. Hence, the product of all three elements will always be 0, and the maximum product is 0.

 

Constraints:

  • 3 <= nums.length <= 105
  • -105 <= nums[i] <= 105

Solutions

Solution 1: Sorting

According to the problem description, we can replace one element in the array with any integer in the range \([-10^5, 10^5]\). To maximize the product of three elements, we can consider the following cases:

  1. Select the two smallest elements in the array and replace the third element with \(10^5\).
  2. Select the two largest elements in the array and replace the third element with \(10^5\).
  3. Select the smallest element and the two largest elements in the array, and replace the middle element with \(-10^5\).

The maximum product among these three cases is the answer.

Therefore, we can first sort the array, then calculate the products for the above three cases, and return the maximum value among them.

The time complexity is \(O(n \log n)\) and the space complexity is \(O(\log n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        a, b = nums[0], nums[1]
        c, d = nums[-2], nums[-1]
        x = 10**5
        return max(a * b * x, c * d * x, a * d * -x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public long maxProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long a = nums[0], b = nums[1];
        long c = nums[n - 2], d = nums[n - 1];
        final int x = 100000;
        return Math.max(Math.max(a * b * x, c * d * x), -a * d * x);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    long long maxProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long a = nums[0], b = nums[1];
        long long c = nums[n - 2], d = nums[n - 1];
        const int x = 100000;
        return max({a * b * x, c * d * x, -a * d * x});
    }
};

1
2
3
4
5
6
7
8
func maxProduct(nums []int) int64 {
    sort.Ints(nums)
    n := len(nums)
    a, b := int64(nums[0]), int64(nums[1])
    c, d := int64(nums[n-2]), int64(nums[n-1])
    const x int64 = 100000
    return max(a*b*x, c*d*x, -a*d*x)
}

1
2
3
4
5
6
7
8
function maxProduct(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const [a, b] = [nums[0], nums[1]];
    const [c, d] = [nums[n - 2], nums[n - 1]];
    const x = 100000;
    return Math.max(a * b * x, c * d * x, -a * d * x);
}

Comments