Maximum product of three elements after one replacement

Array Math Greedy Sorting

47.1% acceptance

Feb 24, 2026

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. Return an integer denoting the maximum product achievable.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(nums: Vec<i32>) -> i64 {
    const MAX_VAL: i64 = 100_000;
    let n = nums.len();
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    let s: Vec<i64> = sorted.iter().map(|&x| x as i64).collect();
    // Best product of 3: replace one of the 3 chosen elements with +/-MAX_VAL
    // Candidates for best product before replacement:
    // - s[n-1]*s[n-2]*s[n-3] (3 largest)
    // - s[0]*s[1]*s[n-1] (2 smallest negatives * largest)
    // After replacement, we replace one of the 3 chosen with MAX_VAL or -MAX_VAL
    // Strategy: try replacing each index in the chosen triple with MAX_VAL and -MAX_VAL
    // Also try choosing 2 elements + replacement as third
    let mut best = i64::MIN;
    let candidates = [MAX_VAL, -MAX_VAL];
    // Try every combination from sorted endpoints:
    let idxs = [0, 1, n - 2, n - 1];
    for &v in &candidates {
      // Pick 2 from endpoints + v
      for i in 0..idxs.len() {
        for j in i+1..idxs.len() {
          if idxs[i] == idxs[j] { continue; }
          best = best.max(s[idxs[i]] * s[idxs[j]] * v);
        }
      }
      // Pick 3 from endpoints, replace one with v
      for i in 0..idxs.len() {
        for j in i+1..idxs.len() {
          for k in j+1..idxs.len() {
            if idxs[i]==idxs[j]||idxs[i]==idxs[k]||idxs[j]==idxs[k] { continue; }
            best = best.max(v * s[idxs[j]] * s[idxs[k]]);
            best = best.max(s[idxs[i]] * v * s[idxs[k]]);
            best = best.max(s[idxs[i]] * s[idxs[j]] * v);
          }
        }
      }
    }
    best
  }
}