Mean of Array After Removing Some Elements: Trimmed Mean
Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements. This is LeetCode 1619: Mean of Array After Removing Some Elements. Answers within 10^-5 of the actual answer are accepted.
The operation described here is called a trimmed mean, and it shows up constantly in real-world statistics. You chop off the outliers from both ends to get a more robust average.
Why this problem matters
Trimmed means are used everywhere in statistics and data analysis. Olympic judges drop the highest and lowest scores before averaging. Economic indicators like the trimmed-mean PCE inflation rate strip out volatile categories. The idea is the same: extreme values can skew the average, so you remove them.
From a coding interview perspective, this problem teaches you to sort an array, compute a slice index using integer division, and iterate over a subarray to compute an aggregate. These are fundamental building blocks that combine in dozens of harder problems.
The key insight
Sort the array. Figure out how many elements to trim from each end: n * 5 // 100, which simplifies to n // 20. Slice out the middle portion (from index trim to index n - trim), and compute the average of those remaining elements.
The constraint guarantees that n is a multiple of 20, so the 5% trim count is always a clean integer. No rounding edge cases to worry about.
The solution
def trimMean(arr: list[float]) -> float:
arr.sort()
trim = len(arr) // 20
trimmed = arr[trim:len(arr) - trim]
return sum(trimmed) / len(trimmed)
You sort the array in-place, compute the number of elements to remove from each end, then slice out the middle. The sum divided by the count gives you the mean. That is the entire solution.
The time complexity is dominated by the sort: O(n log n). The space for the slice is O(n) in Python since slicing creates a new list. You could avoid that extra allocation by iterating with index bounds instead, but for this problem the slice version is cleaner and still passes easily.
Since the problem guarantees n is a multiple of 20, you can use integer division n // 20 directly. If the problem did not guarantee this, you would need int(n * 0.05) or math.floor(n * 0.05) to handle non-integer trim counts. Always check the constraints before deciding how to compute the boundary.
Visual walkthrough
Step 1: Original unsorted array
The input has 20 elements in no particular order.
Step 2: Sort and trim the smallest 1 and largest 1 elements (5% each)
n = 20, so 5% = 20 / 20 = 1. Remove 1 from each end. Red = trimmed, green = kept.
Step 3: Compute the mean of the remaining elements
Sum of 18 kept elements = 72. Mean = 72 / 18 = 4.00000.
The walkthrough makes the three-phase pattern clear: sort, trim, average. Each phase is a single line of code. The only subtlety is computing the trim count correctly, and the constraint that n is divisible by 20 eliminates that subtlety entirely.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Sort + Slice | O(n log n) | O(n) |
The sort is O(n log n). Building the slice is O(n). Computing the sum is O(n). The dominant term is the sort. Space is O(n) for the slice (or O(1) extra if you iterate with indices instead of creating a new list).
Could you do better? Theoretically, you could use a partial sort or selection algorithm to find the trim boundaries in O(n) average time. But for this problem's constraints (20 to 1000 elements), the simplicity of a full sort far outweighs the constant-factor savings of a linear selection approach.
The building blocks
1. Sorting and slicing
arr.sort()
trimmed = arr[trim:len(arr) - trim]
Sorting brings structure to the array: the smallest values cluster at the front, the largest at the back. Slicing then extracts exactly the portion you care about. This sort-then-slice pattern appears in problems like Kth Largest Element, Contains Duplicate, and Merge Intervals. Any time you need to reason about relative order or remove extremes, sorting is your first tool.
2. Computing mean from a subarray
mean = sum(subarray) / len(subarray)
Taking the average of a contiguous portion of an array is a micro-operation that shows up in sliding window problems, moving average calculations, and statistical aggregations. The pattern is always the same: accumulate the sum, divide by the count. In more complex problems, you maintain a running sum and adjust it incrementally instead of recomputing from scratch.
Edge cases
- All elements identical:
arr = [5, 5, 5, ..., 5]. Sorting changes nothing. Trimming removes identical values from both ends. The mean is still 5. Your code handles this naturally. - Minimum array size (n = 20): trim = 1, so you remove one element from each end and average the remaining 18. Make sure your slice indices are correct for the smallest input.
- Already sorted input: the sort is a no-op, but the code still works. No special case needed.
- Negative values: sorting still places them in the correct order. The sum and division work the same way. No sign-related edge cases.
- Large spread in values: an array like
[1, 1, 1, ..., 1, 1000000]has outliers that the trimmed mean is designed to handle. After trimming, the extreme value is gone.
From understanding to recall
You have read the solution and it makes sense. Sort, compute the trim count with integer division, slice, average. Four lines. But when you sit down for an interview and the adrenaline hits, even simple problems can trip you up. Did you divide by 20 or by 10? Do you slice to n - trim or n - trim - 1? Is it len(arr) or len(trimmed) in the denominator?
These are not conceptual gaps. They are recall gaps. Spaced repetition closes them. You write the solution from scratch, check it, and come back in a day. Then three days. Then a week. After a few cycles, the sort-trim-average sequence is automatic. You do not need to rederive it. You just write it.
Related posts
- Sort Colors - Sorting fundamentals with the Dutch National Flag pattern
- Contains Duplicate - Basic sorting-based array analysis
- Kth Largest Element in an Array - Partial sorting and selection
CodeBricks breaks the mean of array after removing some elements LeetCode problem into its sorting, slicing, and aggregation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a trimmed mean or similar statistical array question shows up in your interview, you do not pause to think. You just write it.