Mean of Array After Removing Some Elements
EasyPrompt
Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.
Answers within 10-5 of the actual answer will be considered accepted.
Example 1:
Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.Example 2:
Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000Example 3:
Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778
Constraints:
20 <= arr.length <= 1000arr.lengthis a multiple of20.0 <= arr[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach leverages the constraint that the element values are within a limited range (0 to 100,000). Instead of a comparison-based sort, we can use a counting sort, which has a linear time complexity with respect to the range of values. We count the occurrences of each number, virtually 'remove' the smallest and largest 5% by adjusting their counts, and then calculate the sum of the remaining elements to find the mean.
Algorithm
- Determine the number of elements to trim from each end:
trimCount = arr.length / 20. - Create a frequency array,
counts, of size 100001 to store the frequency of each number inarr. - Iterate through
arrand populate thecountsarray.counts[x]will store the number of timesxappears inarr. - Initialize
sum = 0.0andremainingElements = arr.length - 2 * trimCount. - Initialize two counters,
leftTrimandrightTrim, both totrimCount. - Trim Smallest: Iterate from the smallest possible value (0) upwards. For each number
i, determine how many instances ofito remove. This will bemin(leftTrim, counts[i]). UpdateleftTrimandcounts[i]. Stop whenleftTrimbecomes 0. - Trim Largest: Iterate from the largest possible value (100000) downwards. For each number
j, determine how many instances ofjto remove, which ismin(rightTrim, counts[j]). UpdaterightTrimandcounts[j]. Stop whenrightTrimbecomes 0. - Calculate Sum: Iterate through the modified
countsarray. For each numberk, addk * counts[k]to thesum. - Calculate Mean: The final mean is
sum / remainingElements.
Walkthrough
The core idea is to avoid a full sort by using the values of the elements themselves as indices in a frequency array. This is possible because the values are non-negative and bounded.
First, we create a counts array of size 100001. We iterate through the input arr once to populate this frequency map. For example, counts[10] will store how many times the number 10 appears in arr.
Next, we calculate how many elements to trim from each end, which is 5% of the total length, or arr.length / 20. Let's call this trimCount.
We then perform the trimming. To trim the smallest elements, we iterate from the beginning of our counts array (index 0). We decrement the counts of the numbers we encounter until we have accounted for trimCount elements. Similarly, to trim the largest elements, we iterate from the end of the counts array (index 100000) backwards, decrementing counts until we have accounted for another trimCount elements.
Finally, we iterate through the now-adjusted counts array. We calculate the sum of the remaining elements by multiplying each number i by its remaining count counts[i]. The mean is this total sum divided by the number of remaining elements, which is arr.length - 2 * trimCount.
class Solution { public double trimMean(int[] arr) { int n = arr.length; int[] counts = new int[100001]; for (int num : arr) { counts[num]++; } int trimCount = n / 20; int leftTrim = trimCount; int rightTrim = trimCount; // Trim smallest elements for (int i = 0; i < counts.length && leftTrim > 0; i++) { int toRemove = Math.min(leftTrim, counts[i]); counts[i] -= toRemove; leftTrim -= toRemove; } // Trim largest elements for (int i = counts.length - 1; i >= 0 && rightTrim > 0; i--) { int toRemove = Math.min(rightTrim, counts[i]); counts[i] -= toRemove; rightTrim -= toRemove; } double sum = 0; int remainingElements = 0; for (int i = 0; i < counts.length; i++) { if (counts[i] > 0) { sum += (double)i * counts[i]; remainingElements += counts[i]; } } return sum / remainingElements; }}Complexity
Time
O(N + K), where N is the length of the array and K is the range of possible values (100001). We iterate through the input array once (`O(N)`) and then iterate through the counts array a constant number of times (`O(K)`). For the given constraints (`N <= 1000`, `K = 100001`), this is dominated by `K`.
Space
O(K), where K is the range of possible values in `arr`. In this case, K is 100001, so we need an auxiliary array of this size to store the frequency counts.
Trade-offs
Pros
Has a linear time complexity,
O(N + K), which is very efficient ifKis not significantly larger thanN.Avoids the overhead of comparison-based sorting.
Cons
High space complexity (
O(K)), which can be a problem if the range of values is very large.Inefficient when the range of values
Kis much larger than the number of elementsN, which is the case for this problem's constraints.
Solutions
Solution
class Solution {public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length; double s = 0; for (int start = (int)(n * 0.05), i = start; i < n - start; ++i) { s += arr[i]; } return s / (n * 0.9); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.