4101. Maximum Product of Three Elements After One Replacement

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        MAX_VAL = 10**5
        MIN_VAL = -10**5
        n = len(nums)
        
        # Sort the array
        nums_sorted = sorted(nums)
        
        # Without any replacement, max product is either:
        # - top 3 largest
        # - 2 smallest (most negative) × largest
        
        # With one replacement, we can:
        # 1. Replace a number not in our chosen triple with MAX_VAL or MIN_VAL
        # 2. Replace one of our chosen numbers with MAX_VAL or MIN_VAL
        
        # Strategy: Try all possible ways
        # Case 1: Replace one element to MAX_VAL, then find max product of 3
        # Case 2: Replace one element to MIN_VAL, then find max product of 3
        
        # After replacing one element with MAX_VAL:
        # The new sorted array has one MAX_VAL at the end
        # So max product could be:
        # - MAX_VAL × second_largest × third_largest
        # - MAX_VAL × smallest × second_smallest (if both negative)
        
        # Similarly for MIN_VAL at start
        
        # Let's enumerate: for each position to replace, and each replacement value
        # This is O(n) positions × 2 values × O(n log n) per = O(n^2 log n), too slow
        
        # Better approach:
        # After sorting, consider which 3 to pick and which 1 to modify
        # Key insight: optimal triple uses elements from extremes
        
        # Candidates after sorting: nums_sorted[0], nums_sorted[1], ... , nums_sorted[-2], nums_sorted[-1]
        # Max product triples are typically from {0, 1, n-3, n-2, n-1}
        
        # With modification: we can make any one of these 5 elements into MAX_VAL or MIN_VAL
        
        # Let's consider:
        # 1. Keep indices {n-3, n-2, n-1} and optionally modify one
        # 2. Keep indices {0, 1, n-1} and optionally modify one
        # etc.
        
        # Actually simpler: after replacing one element, the max product triple comes from the new sorted extremes
        # So we try replacing each of the 5 key positions with MAX_VAL or MIN_VAL
        
        # Key positions: indices 0, 1, 2, n-3, n-2, n-1 (overlap if n <= 6)
        key_indices = list(set([0, 1, 2, n-3, n-2, n-1]))
        
        best = float('-inf')
        
        # Try each replacement
        for idx in key_indices:
            for new_val in [MAX_VAL, MIN_VAL]:
                # Create modified array (virtually)
                modified = nums_sorted.copy()
                modified[idx] = new_val
                modified.sort()
                
                # Compute max product of 3
                # Top 3 or 2 smallest × top
                p1 = modified[-1] * modified[-2] * modified[-3]
                p2 = modified[0] * modified[1] * modified[-1]
                best = max(best, p1, p2)
        
        return best