Mean of Array After Removing Some Elements

Easy

#1488Time: 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.

Algorithms

Sorting

Data structures

Array

Prompt

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.00000

Example 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 <= 1000
arr.length is a multiple of 20.
0 <= arr[i] <= 10⁵

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 in arr.
Iterate through arr and populate the counts array. counts[x] will store the number of times x appears in arr.
Initialize sum = 0.0 and remainingElements = arr.length - 2 * trimCount.
Initialize two counters, leftTrim and rightTrim, both to trimCount.
Trim Smallest: Iterate from the smallest possible value (0) upwards. For each number i, determine how many instances of i to remove. This will be min(leftTrim, counts[i]). Update leftTrim and counts[i]. Stop when leftTrim becomes 0.
Trim Largest: Iterate from the largest possible value (100000) downwards. For each number j, determine how many instances of j to remove, which is min(rightTrim, counts[j]). Update rightTrim and counts[j]. Stop when rightTrim becomes 0.
Calculate Sum: Iterate through the modified counts array. For each number k, add k * counts[k] to the sum.
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.

1class Solution {2    public double trimMean(int[] arr) {3        int n = arr.length;4        int[] counts = new int[100001];5        for (int num : arr) {6            counts[num]++;7        }8 9        int trimCount = n / 20;10        int leftTrim = trimCount;11        int rightTrim = trimCount;12 13        // Trim smallest elements14        for (int i = 0; i < counts.length && leftTrim > 0; i++) {15            int toRemove = Math.min(leftTrim, counts[i]);16            counts[i] -= toRemove;17            leftTrim -= toRemove;18        }19 20        // Trim largest elements21        for (int i = counts.length - 1; i >= 0 && rightTrim > 0; i--) {22            int toRemove = Math.min(rightTrim, counts[i]);23            counts[i] -= toRemove;24            rightTrim -= toRemove;25        }26 27        double sum = 0;28        int remainingElements = 0;29        for (int i = 0; i < counts.length; i++) {30            if (counts[i] > 0) {31                sum += (double)i * counts[i];32                remainingElements += counts[i];33            }34        }35 36        return sum / remainingElements;37    }38}

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 if K is not significantly larger than N.
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 K is much larger than the number of elements N, which is the case for this problem's constraints.

The most intuitive and, for these constraints, most efficient approach is to sort the array first. Once the array is sorted, the smallest 5% of elements will be at the beginning of the array, and the largest 5% will be at the end. We can then easily ignore these elements by defining a sub-array (or by using loop bounds) and calculate the sum and mean of the remaining middle 90% of the elements.

Algorithm

Sort the input array arr in non-decreasing order.
Calculate the number of elements to remove from each end: removeCount = arr.length / 20.
The elements we need to consider are in the range of indices from removeCount to arr.length - removeCount - 1.
Initialize a variable sum to 0.0.
Iterate from i = removeCount to arr.length - removeCount - 1 and add arr[i] to sum.
The number of elements included in the sum is arr.length - 2 * removeCount.
Calculate the mean by dividing sum by the count of remaining elements.

Walkthrough

This method relies on a standard sorting algorithm. The logic is straightforward:

Sort: The first step is to sort the entire input array arr in ascending order. Java's Arrays.sort() is a highly optimized implementation suitable for this.
Identify Boundaries: After sorting, the k smallest elements are the first k elements, and the k largest are the last k elements. We calculate k as 5% of the array length, which is removeCount = arr.length / 20.
Summation: We can now ignore the first removeCount elements and the last removeCount elements. We iterate through the array from index removeCount up to (but not including) index arr.length - removeCount. During this iteration, we accumulate the values of the elements into a sum variable.
Calculate Mean: The total number of elements we summed is arr.length - 2 * removeCount. The mean is simply the calculated sum divided by this count of remaining elements.

This approach is efficient because modern sorting algorithms are very fast, and for the given constraints (arr.length <= 1000), an O(N log N) complexity is superior to an O(N + K) approach where K is large (100001).

1import java.util.Arrays;2 3class Solution {4    public double trimMean(int[] arr) {5        // Step 1: Sort the array6        Arrays.sort(arr);7 8        // Step 2: Calculate the number of elements to remove9        int n = arr.length;10        int removeCount = n / 20;11 12        // Step 3: Sum the middle elements13        double sum = 0;14        for (int i = removeCount; i < n - removeCount; i++) {15            sum += arr[i];16        }17 18        // Step 4: Calculate the mean19        int remainingElements = n - 2 * removeCount;20        return sum / remainingElements;21    }22}

Complexity

Time

O(N log N), where N is the length of the array. This is dominated by the sorting step. The subsequent loop to calculate the sum runs in `O(N)`, which is less significant.

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives uses a dual-pivot quicksort which has an average space complexity of `O(log N)`.

Trade-offs

Pros

Conceptually simple and easy to implement.
More efficient than counting sort for the given constraints where N is relatively small and the range of values K is large.
Space-efficient, as in-place sorting algorithms have low space overhead.

Cons

Can be slower than linear time algorithms if N is very large and the range of values is small.

Solutions

Solution

1class Solution {2public3  double trimMean(int[] arr) {4    Arrays.sort(arr);5    int n = arr.length;6    double s = 0;7    for (int start = (int)(n * 0.05), i = start; i < n - start; ++i) {8      s += arr[i];9    }10    return s / (n * 0.9);11  }12}

1class Solution {2public:3  double trimMean(vector<int> &arr) {4    sort(arr.begin(), arr.end());5    int n = arr.size();6    double s = 0;7    for (int start = (int)(n * 0.05), i = start; i < n - start; ++i)8      s += arr[i];9    return s / (n * 0.9);10  }11};

1class Solution:2    def trimMean(self, arr: List[int]) -> float: n = len(arr) start, end = int(n * 0.05), int(n * 0.95) arr . sort() t = arr[start: end] return round(sum(t) / len(t), 5)

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.

← Previous

Previous problem

Next problem