python
# Pseudo-code for Brute Force
def brute_force(nums):
    while True:
        found_pair = False
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                # Remove pair and rebuild array
                nums = nums[:i] + nums[i+2:]
                found_pair = True
                break # Restart scan
        if not found_pair:
            break
    
    if not nums: return 0.0
    return sum(nums) / len(nums)

Time Complexity: $O(N^2)$. In the worst case (e.g., [1, 2, 3, ..., 3, 2, 1]), we remove one pair at a time. Removing elements from an array (shifting) takes $O(N)$, and we might do this $N/2$ times. Why it fails: The constraints for typical interview problems ($N \approx 10^5$) make an $O(N^2)$ solution result in a Time Limit Exceeded (TLE) error.

Core Insight for Calculate Compressed Mean

The key intuition is that we don't need to restart the scan after every removal. The "compression" only affects the boundary between the processed prefix and the remaining suffix.

When we iterate through nums, we maintain a collection of "surviving" elements (the compressed array so far). For each new element in our iteration (the "sliding" pointer), we only need to look at the last surviving element.

1. If the current element equals the last surviving element, they form a pair [x, x]. Both are annihilated. The last surviving element is removed, and the current element is ignored.
2. If they are different (or there are no survivors yet), the current element survives and is added to our collection.

This logic enforces the invariant that the "surviving" list never contains adjacent duplicates. By maintaining this invariant incrementally, we avoid the $O(N^2)$ re-scanning.

Visual Description: Imagine a window focused on the "gap" between the processed list and the unprocessed list.

• Left side of window: The last element of our compressed result (Top of Stack).
• Right side of window: The current element from nums we are processing.
• The algorithm compares these two. If they match, the window "closes" (both disappear). If they differ, the Right element moves into the Left side. This effectively slides through the array once.

Execution Flow

Let's trace nums = [1, 2, 2, 1, 3].

1. Start: compressed = [].
2. Process 1:
   • compressed is empty.
   • Action: Push 1.
   • compressed = [1]
3. Process 2:
   • Window: [1, 2] (compare last element 1 with current 2).
   • 1 != 2.
   • Action: Push 2.
   • compressed = [1, 2]
4. Process 2:
   • Window: [2, 2] (compare last element 2 with current 2).
   • 2 == 2. Match found!
   • Action: Pop 2. Ignore current 2.
   • compressed = [1]
5. Process 1:
   • Window: [1, 1] (compare last element 1 with current 1).
   • 1 == 1. Match found!
   • Action: Pop 1. Ignore current 1.
   • compressed = []
6. Process 3:
   • compressed is empty.
   • Action: Push 3.
   • compressed = [3]
7. End: Sum = 3, Count = 1. Mean = 3.0.

Proof of Correctness

The algorithm is correct because of the associative property of the removal operation. Removing an adjacent pair [x, x] does not affect the relative order of the elements surrounding it. By processing left-to-right and canceling immediately upon detection, we ensure that any new adjacency created (like the 1, 1 pair in the example above) is detected as soon as the inner pair (2, 2) is removed. The compressed list always represents the fully reduced state of the prefix processed so far.

Reference Implementation

C++ Solution for LeetCode 2985

cpp
#include <vector>
#include <numeric>
#include <iomanip>

class Solution {
public:
    double calculateCompressedMean(std::vector<int>& nums) {
        std::vector<int> compressed;
        
        for (int num : nums) {
            // Check fixed-size window: [back of compressed, current num]
            if (!compressed.empty() && compressed.back() == num) {
                compressed.pop_back(); // Remove the pair
            } else {
                compressed.push_back(num); // Add to survivors
            }
        }
        
        if (compressed.empty()) {
            return 0.0;
        }
        
        // Calculate mean using long long to prevent overflow during sum
        long long sum = 0;
        for (int val : compressed) {
            sum += val;
        }
        
        return (double)sum / compressed.size();
    }
};

Java Solution for LeetCode 2985

java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public double calculateCompressedMean(int[] nums) {
        // Use ArrayList as a stack for the compressed elements
        List<Integer> compressed = new ArrayList<>();
        
        for (int num : nums) {
            // Check fixed-size window: [last element, current num]
            int size = compressed.size();
            if (size > 0 && compressed.get(size - 1) == num) {
                compressed.remove(size - 1); // Remove the pair
            } else {
                compressed.add(num); // Add to survivors
            }
        }
        
        if (compressed.isEmpty()) {
            return 0.0;
        }
        
        long sum = 0;
        for (int val : compressed) {
            sum += val;
        }
        
        return (double) sum / compressed.size();
    }
}

Python Solution for LeetCode 2985

python
class Solution:
    def calculateCompressedMean(self, nums: list[int]) -> float:
        compressed = []
        
        for num in nums:
            # Check fixed-size window: [compressed[-1], num]
            if compressed and compressed[-1] == num:
                compressed.pop() # Pair detected, remove both
            else:
                compressed.append(num)
        
        if not compressed:
            return 0.0
            
        return sum(compressed) / len(compressed)