Naive Solution

The most straightforward approach is to sort the array and then calculate the mean of the remaining elements after removing the smallest 5% and the largest 5%.

1. Sort the input array arr.
2. Calculate the number of elements to remove from each end: n = arr.length, k = n * 5 / 100.
3. Sum the elements from index k to n - k - 1.
4. Divide the sum by n - 2 * k to get the mean.

import java.util.Arrays;

class Solution {
    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        int k = n * 5 / 100;
        double sum = 0;
        for (int i = k; i < n - k; i++) {
            sum += arr[i];
        }
        return sum / (n - 2 * k);
    }
}

• Time Complexity: O(n log n) due to the sorting step.
• Space Complexity: O(1) or O(n) depending on the sorting algorithm implementation (in-place or creating a copy).

Optimal Solution

An optimized approach avoids full sorting by using a counting sort (since the problem states 0 <= arr[i] <= 10^5). This is efficient because we can count the occurrences of each number and skip the smallest and largest 5% when calculating the sum. Since the range of numbers are limited, this is preferable to sorting the array.

1. Create a counting array count of size 100001 (as 0 <= arr[i] <= 10^5).
2. Populate the count array by iterating through arr.
3. Calculate the number of elements to remove from each end: n = arr.length, k = n * 5 / 100.
4. Iterate from 0 to 100000, adding each number i to the sum count[i] times, while keeping track of how many numbers have been added to the sum. Skip the smallest and largest 5% using the counter k.
5. Return the mean.

class Solution {
    public double trimMean(int[] arr) {
        int n = arr.length;
        int k = n * 5 / 100;
        int[] count = new int[100001];
        for (int x : arr) {
            count[x]++;
        }

        double sum = 0;
        int numCounted = 0;

        // Remove smallest 5%
        int removed = 0;
        for (int i = 0; i < count.length && removed < k; i++) {
            int toRemove = Math.min(count[i], k - removed);
            removed += toRemove;
            count[i] -= toRemove;
        }

        // Sum remaining numbers
        for (int i = 0; i < count.length; i++) {
            sum += (double) i * count[i];
            numCounted += count[i];
        }

        // Remove largest 5%
        removed = 0;
        for (int i = count.length - 1; i >= 0 && removed < k; i--) {
            int toRemove = Math.min(count[i], k - removed);
            removed += toRemove;
            count[i] -= toRemove;
        }

        

        return sum / (n - 2 * k);
    }
}

• Time Complexity: O(n + m), where n is the length of the input array, and m is the range of numbers (100001). In many cases, n will be greater than m. So O(n) would also be a good estimate.
• Space Complexity: O(m), where m is the range of numbers (100001).

Edge Cases

• Empty Array: The problem statement says 20 <= arr.length <= 1000, so we don't need to consider this.
• All elements are the same: Should work fine.
• Large range of numbers: The constraint 0 <= arr[i] <= 10^5 is important; if the range was unbounded, sorting would be better.
• Zero elements to remove (k = 0): This is possible if arr.length = 20. The division should still give the correct mean.