Calculate Compressed Mean

LeetCode 2985: Calculate Compressed Mean Solution & Explanation

Problem Overview

TL;DR: Iterate through the array using a stack-like simulation to cancel out adjacent equal pairs in a single pass ($O(N)$), then calculate the mean of the remaining elements.

The problem asks us to process an integer array nums by repeatedly removing adjacent pairs of equal values. This process simulates a chain reaction: removing a pair might bring two other equal values together, requiring further removals. Once the array is fully "compressed" (no adjacent equal pairs remain), we must calculate and return the mean (average) of the remaining elements. If the array becomes empty, the result is 0.0.

This is a popular interview question that tests your ability to optimize a recursive reduction process into a linear scan.

Brute Force Approach for Calculate Compressed Mean

The naive approach directly simulates the problem statement instructions. We repeatedly scan the array to find the first occurrence of nums[i] == nums[i+1]. When found, we create a new array excluding these two elements and restart the scan from the beginning. We repeat this until no adjacent equal pairs exist.

1# Pseudo-code for Brute Force
2def brute_force(nums):
3    while True:
4        found_pair = False
5        for i in range(len(nums) - 1):
6            if nums[i] == nums[i+1]:
7                # Remove pair and rebuild array
8                nums = nums[:i] + nums[i+2:]
9                found_pair = True
10                break # Restart scan
11        if not found_pair:
12            break
13    
14    if not nums: return 0.0
15    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.

Algorithm Strategy: Sliding Window Patterns

To implement this efficiently, we use a dynamic array (or stack) to store the compressed result.

1. Initialize Storage: Create a list compressed to act as our accumulated survivors.
2. Iterate (Slide): Loop through each number num in the input nums.
3. Fixed Size Comparison: Check the relationship between num and the last element of compressed.
   • This check represents a window of size 2: [compressed.back(), num].
4. Update State:
   • If compressed is not empty AND compressed.back() == num: We found a pair. Remove the last element from compressed. Do not add num.
   • Otherwise: num is stable (for now). Add it to compressed.
5. Final Calculation: Once the loop finishes, if compressed is empty, return 0.0. Otherwise, calculate the sum of compressed divided by its size.

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.

Pattern Reuse Notes

The logic of maintaining a running state or window as we iterate is a fundamental pattern.

• LeetCode 346: Moving Average from Data Stream: Uses a queue (FIFO window) to calculate the mean of the last K elements.
• LeetCode 643: Maximum Average Subarray I: Uses a fixed-size sliding window to find the subarray with the largest mean.
• LeetCode 3254: Find the Power of K-Size Subarrays I: Iterates through subarrays of size K to check properties.
• LeetCode 3318: Find X-Sum of All K-Long Subarrays I: Maintains complex state (frequency counts) within a sliding window.

While LeetCode 2985 uses a "stack-like" frontier, it shares the core "single pass with state maintenance" philosophy found in these sliding window problems.

Reference Implementation

C++ Solution for LeetCode 2985

1#include <vector>
2#include <numeric>
3#include <iomanip>
4
5class Solution {
6public:
7    double calculateCompressedMean(std::vector<int>& nums) {
8        std::vector<int> compressed;
9        
10        for (int num : nums) {
11            // Check fixed-size window: [back of compressed, current num]
12            if (!compressed.empty() && compressed.back() == num) {
13                compressed.pop_back(); // Remove the pair
14            } else {
15                compressed.push_back(num); // Add to survivors
16            }
17        }
18        
19        if (compressed.empty()) {
20            return 0.0;
21        }
22        
23        // Calculate mean using long long to prevent overflow during sum
24        long long sum = 0;
25        for (int val : compressed) {
26            sum += val;
27        }
28        
29        return (double)sum / compressed.size();
30    }
31};

Java Solution for LeetCode 2985

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public double calculateCompressedMean(int[] nums) {
6        // Use ArrayList as a stack for the compressed elements
7        List<Integer> compressed = new ArrayList<>();
8        
9        for (int num : nums) {
10            // Check fixed-size window: [last element, current num]
11            int size = compressed.size();
12            if (size > 0 && compressed.get(size - 1) == num) {
13                compressed.remove(size - 1); // Remove the pair
14            } else {
15                compressed.add(num); // Add to survivors
16            }
17        }
18        
19        if (compressed.isEmpty()) {
20            return 0.0;
21        }
22        
23        long sum = 0;
24        for (int val : compressed) {
25            sum += val;
26        }
27        
28        return (double) sum / compressed.size();
29    }
30}

Python Solution for LeetCode 2985

1class Solution:
2    def calculateCompressedMean(self, nums: list[int]) -> float:
3        compressed = []
4        
5        for num in nums:
6            # Check fixed-size window: [compressed[-1], num]
7            if compressed and compressed[-1] == num:
8                compressed.pop() # Pair detected, remove both
9            else:
10                compressed.append(num)
11        
12        if not compressed:
13            return 0.0
14            
15        return sum(compressed) / len(compressed)