# Mean of Array After Removing Some Elements
**Difficulty:** EASY
[External](https://leetcode.com/problems/mean-of-array-after-removing-some-elements)
Canonical: https://scaleengineer.com/dsa/problems/mean-of-array-after-removing-some-elements
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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] <= 105`

# Approaches
## Counting Sort
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Sorting
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.
**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)`.
**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.
### Explanation
This method relies on a standard sorting algorithm. The logic is straightforward:

1.  **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.

2.  **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`.

3.  **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.

4.  **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).

```java
import java.util.Arrays;

class Solution {
    public double trimMean(int[] arr) {
        // Step 1: Sort the array
        Arrays.sort(arr);

        // Step 2: Calculate the number of elements to remove
        int n = arr.length;
        int removeCount = n / 20;

        // Step 3: Sum the middle elements
        double sum = 0;
        for (int i = removeCount; i < n - removeCount; i++) {
            sum += arr[i];
        }

        // Step 4: Calculate the mean
        int remainingElements = n - 2 * removeCount;
        return sum / remainingElements;
    }
}
```
### 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  double trimMean(vector<int> &arr) {
    sort(arr.begin(), arr.end());
    int n = arr.size();
    double s = 0;
    for (int start = (int)(n * 0.05), i = start; i < n - start; ++i)
      s += arr[i];
    return s / (n * 0.9);
  }
};

```

### Python

```python
class Solution:
    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)

```