Maximum Product of Three Elements After One Replacement - Solution & Explanation

Problem Overview: You are given an integer array and allowed to replace exactly one element with another value that maximizes the product of any three elements. The goal is to compute the largest possible product of three numbers after performing at most one optimal replacement.

The tricky part is that the maximum product of three numbers does not always come from the three largest values. Two large negative numbers multiplied with a large positive number can produce a larger result. Because of this, the solution focuses on extreme values in the array.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct method is to try every possible triplet of indices and compute their product. To simulate the replacement, you would also test variations where one of the elements in the triplet is replaced with another candidate value. This requires three nested loops to generate all triplets and additional checks for replacement scenarios. The method guarantees correctness but quickly becomes impractical for large arrays since the number of combinations grows as O(n^3). Space usage stays O(1) because only a few variables are needed to track the maximum product.

Approach 2: Greedy with Sorting (O(n log n) time, O(1) space)

A more practical approach relies on sorting. After sorting the array, the elements that can produce the maximum product must come from the extremes of the sorted list. Specifically, there are two important candidate combinations: the three largest numbers, or the largest number combined with the two smallest numbers (which may both be negative). Sorting places these candidates in predictable positions, allowing you to evaluate them in constant time.

When considering one replacement, the greedy insight is that the optimal modification will push one of the extreme values even further in the direction that benefits the product. That means the final optimal triplet will still be formed from numbers near the start or end of the sorted array. Instead of evaluating every replacement explicitly, compute the candidate products formed by these extreme values and track the maximum. This works because any optimal configuration must include either the largest values or the pair of most negative values.

The algorithm sorts the array, evaluates the candidate products using values at the edges, and returns the largest result. Sorting costs O(n log n), while the product checks run in constant time. Space usage remains O(1) if sorting is done in place.

Conceptually, this is a greedy observation layered on top of array manipulation: the optimal product always emerges from extreme values, not the middle of the list. The math behind negative multiplication explains why the smallest numbers must also be considered, connecting the logic to basic math properties.

Recommended for interviews: Interviewers typically expect the sorting-based greedy solution. A brute force explanation shows you understand the search space, but recognizing that only extreme values matter demonstrates algorithmic insight. The O(n log n) sorting approach is concise, easy to implement, and reliably handles negative numbers and edge cases.