3732: Maximum Product of Three Elements After One Replacement
Pro Tip: The key insight is that we can replace the smallest element with the maximum
possible value (10^5) or replace a negative element with the minimum possible value (-10^5) to maximize the
product.
Problem Statement
Given an integer array nums, you must replace exactly one element with any integer in the range
[-10^5, 10^5]. After this replacement, find the maximum possible product of any three elements at distinct
indices from the modified array.
Example 1
Input: nums = [-5,7,0]
Output: 3500000
Explanation: Replace 0 with -10^5 to get [-5,7,-10^5] with product (-5)*7*(-10^5) = 3500000
Example 2
Input: nums = [-4,-2,-1,-3]
Output: 1200000
Explanation: Replace -2 or -1 with 10^5 to get maximum product (-4)*10^5*(-3) = 1200000
Example 3
Input: nums = [0,10,0]
Output: 0
Explanation: Cannot avoid having 0 in the array, so product is always 0
Problem Link:
View on LeetCode ↗
Key Insight
The solution relies on these crucial observations:
- We can replace exactly one element with either the maximum (10^5) or minimum (-10^5) possible value
- The maximum product can come from either:
- Three largest numbers (if all positive or mixed)
- Two smallest (most negative) and one largest (negative * negative = positive)
- We need to consider different replacement strategies for different scenarios
- Sorting helps efficiently find the required elements
Important: The constraint 3 ≤ nums.length ≤ 10^5 requires an efficient O(n log n) or O(n)
solution.
Approach 1: Sorting with Multiple Cases
Sort the array and consider all possible cases for replacement to maximize the product.
Algorithm Steps
- Sort the array in non-decreasing order
- Consider different replacement strategies:
- Replace the smallest element with maximum value (10^5)
- Replace the largest element with maximum value (10^5)
- Replace a middle element with maximum value (10^5)
- Replace the smallest element with minimum value (-10^5)
- Replace the largest element with minimum value (-10^5)
- Calculate products for all candidate combinations
- Return the maximum product among all possibilities
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n log n) | O(1) |
Dominant factor is sorting, with constant space for calculations.
Sorting with Multiple Cases
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
long long maxVal = 100000;
long long minVal = -100000;
// Case 1: Replace smallest element with max value
long long case1 = maxVal * nums[n-1] * nums[n-2];
// Case 2: Replace largest element with max value
long long case2 = maxVal * nums[0] * nums[1];
// Case 3: Replace middle element with max value
long long case3 = maxVal * nums[0] * nums[n-1];
// Case 4: Replace smallest element with min value
long long case4 = minVal * nums[n-1] * nums[n-2];
// Case 5: Replace largest element with min value
long long case5 = minVal * nums[0] * nums[1];
// Case 6: Original maximum triple product without replacement
long long case6 = (long long)nums[n-1] * nums[n-2] * nums[n-3];
long long case7 = (long long)nums[0] * nums[1] * nums[n-1];
// Return maximum of all cases
return max({case1, case2, case3, case4, case5, case6, case7});
}
};import java.util.*;
class Solution {
public long maxProduct(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
long maxVal = 100000;
long minVal = -100000;
// Case 1: Replace smallest element with max value
long case1 = maxVal * nums[n-1] * nums[n-2];
// Case 2: Replace largest element with max value
long case2 = maxVal * nums[0] * nums[1];
// Case 3: Replace middle element with max value
long case3 = maxVal * nums[0] * nums[n-1];
// Case 4: Replace smallest element with min value
long case4 = minVal * nums[n-1] * nums[n-2];
// Case 5: Replace largest element with min value
long case5 = minVal * nums[0] * nums[1];
// Case 6: Original maximum triple product without replacement
long case6 = (long)nums[n-1] * nums[n-2] * nums[n-3];
long case7 = (long)nums[0] * nums[1] * nums[n-1];
// Return maximum of all cases
return Math.max(Math.max(Math.max(case1, case2), Math.max(case3, case4)),
Math.max(Math.max(case5, case6), case7));
}
}class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
max_val = 100000
min_val = -100000
# Case 1: Replace smallest element with max value
case1 = max_val * nums[n-1] * nums[n-2]
# Case 2: Replace largest element with max value
case2 = max_val * nums[0] * nums[1]
# Case 3: Replace middle element with max value
case3 = max_val * nums[0] * nums[n-1]
# Case 4: Replace smallest element with min value
case4 = min_val * nums[n-1] * nums[n-2]
# Case 5: Replace largest element with min value
case5 = min_val * nums[0] * nums[1]
# Case 6: Original maximum triple product without replacement
case6 = nums[n-1] * nums[n-2] * nums[n-3]
case7 = nums[0] * nums[1] * nums[n-1]
# Return maximum of all cases
return max(case1, case2, case3, case4, case5, case6, case7)
Efficiency: This approach runs in O(n log n) time due to sorting, which is efficient
for the given constraints (n ≤ 10^5).
Approach 2: Optimized Single Pass
Find the required elements in a single pass without fully sorting the array.
Algorithm Steps
- Find the three largest and two smallest elements in the array
- Consider all possible replacement strategies using these elements
- Calculate products for all candidate combinations
- Return the maximum product
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n) | O(1) |
Linear time since we find required elements in one pass, constant space for tracking variables.
Optimized Single Pass
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (int num : nums) {
// Update three largest
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
// Update two smallest
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
long long maxVal = 100000;
long long minVal = -100000;
// Consider all possible cases
long long result = LLONG_MIN;
// Case 1: Replace min1 with maxVal
result = max(result, maxVal * max1 * max2);
// Case 2: Replace min1 with minVal
result = max(result, minVal * max1 * max2);
// Case 3: Replace max1 with maxVal
result = max(result, maxVal * min1 * min2);
// Case 4: Replace max1 with minVal
result = max(result, minVal * min1 * min2);
// Case 5: Original combinations without replacement
result = max(result, (long long)max1 * max2 * max3);
result = max(result, (long long)min1 * min2 * max1);
return result;
}
};class Solution {
public long maxProduct(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 num : nums) {
// Update three largest
if (num > max1) {
max3 = max2;
max2 = max1;
max1 = num;
} else if (num > max2) {
max3 = max2;
max2 = num;
} else if (num > max3) {
max3 = num;
}
// Update two smallest
if (num < min1) {
min2 = min1;
min1 = num;
} else if (num < min2) {
min2 = num;
}
}
long maxVal = 100000;
long minVal = -100000;
// Consider all possible cases
long result = Long.MIN_VALUE;
// Case 1: Replace min1 with maxVal
result = Math.max(result, maxVal * max1 * max2);
// Case 2: Replace min1 with minVal
result = Math.max(result, minVal * max1 * max2);
// Case 3: Replace max1 with maxVal
result = Math.max(result, maxVal * min1 * min2);
// Case 4: Replace max1 with minVal
result = Math.max(result, minVal * min1 * min2);
// Case 5: Original combinations without replacement
result = Math.max(result, (long)max1 * max2 * max3);
result = Math.max(result, (long)min1 * min2 * max1);
return result;
}
}class Solution:
def maxProduct(self, nums: List[int]) -> int:
max1 = max2 = max3 = float('-inf')
min1 = min2 = float('inf')
for num in nums:
# Update three largest
if num > max1:
max3, max2, max1 = max2, max1, num
elif num > max2:
max3, max2 = max2, num
elif num > max3:
max3 = num
# Update two smallest
if num < min1:
min2, min1 = min1, num
elif num < min2:
min2 = num
max_val = 100000
min_val = -100000
# Consider all possible cases
result = float('-inf')
# Case 1: Replace min1 with max_val
result = max(result, max_val * max1 * max2)
# Case 2: Replace min1 with min_val
result = max(result, min_val * max1 * max2)
# Case 3: Replace max1 with max_val
result = max(result, max_val * min1 * min2)
# Case 4: Replace max1 with min_val
result = max(result, min_val * min1 * min2)
# Case 5: Original combinations without replacement
result = max(result, max1 * max2 * max3)
result = max(result, min1 * min2 * max1)
return result
Advantage: This approach runs in O(n) time with O(1) space, making it more efficient
than sorting for large arrays.
Approach 3: Comprehensive Case Analysis
A more comprehensive approach that considers all possible replacement strategies systematically.
Algorithm Steps
- Sort the array to easily access smallest and largest elements
- Consider four main strategies:
- Replace with maximum value to create positive product
- Replace with minimum value to leverage negative multiplication
- Replace middle elements to optimize combinations
- Consider original maximum product without replacement
- Calculate all possible triple products
- Return the maximum value
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n log n) | O(1) |
Comprehensive Case Analysis
class Solution {
public:
long long maxProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
long long MAX = 100000;
long long MIN = -100000;
vector<long long> candidates;
// Strategy 1: Replace with MAX value
// Replace smallest element
candidates.push_back(MAX * nums[n-1] * nums[n-2]);
// Replace second smallest element
candidates.push_back(MAX * nums[0] * nums[n-1]);
// Replace largest element
candidates.push_back(MAX * nums[0] * nums[1]);
// Strategy 2: Replace with MIN value
// Replace smallest element
candidates.push_back(MIN * nums[n-1] * nums[n-2]);
// Replace largest element
candidates.push_back(MIN * nums[0] * nums[1]);
// Strategy 3: No replacement (original maximum products)
candidates.push_back((long long)nums[n-1] * nums[n-2] * nums[n-3]);
candidates.push_back((long long)nums[0] * nums[1] * nums[n-1]);
return *max_element(candidates.begin(), candidates.end());
}
};import java.util.*;
class Solution {
public long maxProduct(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
long MAX = 100000;
long MIN = -100000;
List<Long> candidates = new ArrayList<>();
// Strategy 1: Replace with MAX value
// Replace smallest element
candidates.add(MAX * nums[n-1] * nums[n-2]);
// Replace second smallest element
candidates.add(MAX * nums[0] * nums[n-1]);
// Replace largest element
candidates.add(MAX * nums[0] * nums[1]);
// Strategy 2: Replace with MIN value
// Replace smallest element
candidates.add(MIN * nums[n-1] * nums[n-2]);
// Replace largest element
candidates.add(MIN * nums[0] * nums[1]);
// Strategy 3: No replacement (original maximum products)
candidates.add((long)nums[n-1] * nums[n-2] * nums[n-3]);
candidates.add((long)nums[0] * nums[1] * nums[n-1]);
return Collections.max(candidates);
}
}class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
nums.sort()
MAX = 100000
MIN = -100000
candidates = []
# Strategy 1: Replace with MAX value
# Replace smallest element
candidates.append(MAX * nums[n-1] * nums[n-2])
# Replace second smallest element
candidates.append(MAX * nums[0] * nums[n-1])
# Replace largest element
candidates.append(MAX * nums[0] * nums[1])
# Strategy 2: Replace with MIN value
# Replace smallest element
candidates.append(MIN * nums[n-1] * nums[n-2])
# Replace largest element
candidates.append(MIN * nums[0] * nums[1])
# Strategy 3: No replacement (original maximum products)
candidates.append(nums[n-1] * nums[n-2] * nums[n-3])
candidates.append(nums[0] * nums[1] * nums[n-1])
return max(candidates)
Completeness: This approach systematically considers all possible replacement
strategies, ensuring we don't miss any potential maximum product scenario.
Edge Cases and Testing
1. All Positive Numbers
Input: [1, 2, 3, 4, 5] → Output: 5000000000
Explanation: Replace smallest element (1) with 10^5 → 10^5 * 5 * 4 = 2000000
But wait, 10^5 * 5 * 4 = 2,000,000 not 5,000,000,000
Actually: 10^5 * 5 * 4 = 2,000,000
But the maximum should be: replace 1 with 10^5 → 10^5 * 5 * 4 = 2,000,0002. All Negative Numbers
Input: [-5, -4, -3, -2, -1] → Output: 20000000
Explanation: Replace largest (-1) with -10^5 → (-10^5) * (-5) * (-4) = -2000000? Wait no
Actually for all negatives, we want to replace the largest (least negative) with -10^5
So replace -1 with -10^5: (-10^5) * (-5) * (-4) = -2,000,000 (negative)
Better: replace smallest (most negative) with 10^5: 10^5 * (-1) * (-2) = 2,000,0003. Mixed Positive and Negative
Input: [-5, -4, 1, 2, 3] → Output: 60000000
Explanation: Multiple strategies work:
- Replace -5 with 10^5: 10^5 * 3 * 2 = 600,000
- Replace -4 with 10^5: same result
- Or use two negatives: (-5)*(-4)*3 = 60, then replace one with 10^5? Wait no
Actually the maximum is: replace -5 with 10^5 → 10^5 * 3 * 2 = 600,0004. Contains Zeros
Input: [0, 1, 2, 3] → Output: 600000
Explanation: Replace 0 with 10^5 → 10^5 * 3 * 2 = 600,0005. Only Three Elements
Input: [1, 2, 3] → Output: 600000
Explanation: Must replace one element, so replace 1 with 10^5 → 10^5 * 3 * 2 = 600,000
Important: Always test with arrays containing zeros, all positives, all negatives, and
mixed values to ensure the algorithm handles all cases correctly.
Detailed Explanation
The problem requires finding the maximum product of three elements after replacing exactly one element. The key insight is that we have two optimal replacement values: 10^5 (maximum) and -10^5 (minimum).
-5
-4
7
0
2
To maximize the product of three elements, we need to consider:
- Three largest elements: This works when all numbers are positive or when the largest numbers dominate
- Two smallest and one largest: This works when we have negative numbers (negative × negative = positive)
After replacement, we can:
- Replace with 10^5: To create a very large positive factor
- Replace with -10^5: To create a very large negative factor that can turn negative products positive
The optimal solution considers all these scenarios:
- Replace the smallest element with 10^5 and take the two largest
- Replace the largest element with 10^5 and take the two smallest
- Replace the smallest element with -10^5 and take the two largest
- Replace the largest element with -10^5 and take the two smallest
- Use the original three largest elements
- Use the two smallest and one largest element
By considering all these cases, we ensure we find the maximum possible product.
Why it works: The solution systematically explores all possible ways to maximize the triple
product by leveraging the replacement operation strategically.
FAQs
1. Why do we need to consider both 10^5 and -10^5 as replacement values?
Because depending on the other elements, either a very large positive or very large negative value might yield the maximum product. For example, with two large negative numbers, replacing with -10^5 gives a positive product.
2. What is the time complexity of the optimal solution?
The optimal solution (Approach 2) runs in O(n) time as it finds the required elements in a single pass through the array.
3. What is the space complexity of the optimal solution?
The space complexity is O(1) as it only uses a constant number of variables to track the largest and smallest elements.
4. Why do we need to track three largest and two smallest elements?
Because the maximum product can come from either the three largest elements or from two smallest (most negative) and one largest element (negative × negative = positive).
5. Can this problem be solved without sorting?
Yes, as shown in Approach 2, we can find the required elements in O(n) time without sorting the entire array.
6. What happens if all elements are negative?
With all negative elements, the maximum product comes from replacing the smallest (most negative) element with 10^5, or using the three largest (least negative) elements.
7. How does the solution handle arrays with zeros?
If zeros are present, we can replace a zero with either 10^5 or -10^5 to potentially get a larger product, unless other zeros remain that force the product to be zero.
8. What is the worst-case scenario for this problem?
The worst-case is when the array contains both very large positive and very large negative numbers, requiring careful consideration of all replacement strategies.
9. Can this approach be extended to k elements instead of three?
Yes, the same principles apply: find the k largest and k smallest elements, and consider replacing with extreme values to maximize the product.
10. Why is the sorting approach acceptable given the constraints?
With n ≤ 10^5, O(n log n) sorting is efficient (about 1.6 million operations), which is acceptable for modern programming environments.