Problem Description

Given an integer array arr and an integer k, your task is to calculate the mean (average) of the array after removing the smallest k elements and the largest k elements. The mean should be returned as a floating-point number. You must not reuse or double-count any elements, and there is always at least one valid solution (i.e., the array is large enough so that after removing 2k elements, at least one remains).

Constraints:

• 1 ≤ arr.length ≤ 1000
• 1 ≤ k < arr.length / 2
• Do not reuse or double-count elements.
• There is always at least one element remaining after removals.

Thought Process

The first thought is to literally remove the k smallest and k largest elements and then compute the mean of what's left. Brute-force would sort the array, slice off the ends, and average the rest. The constraints are small, so a sort is acceptable. However, we should always consider if there's a more efficient way, especially if the problem size were larger.

Since the problem requires removing elements from both ends, sorting is the most direct and reliable method. We don't need to worry about duplicate values or in-place operations, as we can use sorting and slicing. This approach is both simple and effective.

Solution Approach

Here is the step-by-step algorithm to solve this problem:

1. Sort the array arr: Sorting arranges all elements in ascending order, making it easy to remove the smallest and largest values.
2. Remove the smallest and largest k elements: After sorting, the first k elements are the smallest, and the last k are the largest. We can exclude these by slicing the array from index k to len(arr) - k.
3. Calculate the mean: Sum the remaining elements and divide by their count to get the mean as a floating-point number.

This approach is simple and leverages built-in language features for sorting and slicing, making it both readable and efficient for the given constraints.

Example Walkthrough

Let's walk through an example:

• Input: arr = [6, 2, 7, 5, 1, 2, 0, 10, 3, 9], k = 2
• Step 1 (Sort): arr = [0, 1, 2, 2, 3, 5, 6, 7, 9, 10]
• Step 2 (Remove smallest and largest 2): Remove [0, 1] (smallest 2) and [9, 10] (largest 2). Remaining: [2, 2, 3, 5, 6, 7]
• Step 3 (Compute mean): Sum = 2 + 2 + 3 + 5 + 6 + 7 = 25. Count = 6. Mean = 25 / 6 ≈ 4.1667

The final answer is approximately 4.1667.

Time and Space Complexity

• Brute-force approach: If we searched for the k smallest and largest elements in O(n) time each, it would be O(kn), but that's unnecessary here.
• Optimized approach: Sorting the array is O(n log n). Slicing and summing the middle section is O(n). So overall, the time complexity is O(n log n).
• Space Complexity: Sorting may use O(n) extra space depending on the language implementation. Slicing creates a subarray, which is also O(n) in the worst case.

Summary

The key insight is to sort the array, remove the smallest and largest k elements, and average the rest. This approach is both intuitive and efficient for the problem constraints. Sorting simplifies the removal process, and slicing ensures we do not double-count or reuse elements. The solution is elegant due to its simplicity and directness.

Code Implementation

class Solution:
    def trimMean(self, arr: List[int], k: int) -> float:
        arr.sort()
        trimmed = arr[k:len(arr)-k]
        return sum(trimmed) / len(trimmed)
      

class Solution {
public:
    double trimMean(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int sum = 0;
        for (int i = k; i < n - k; ++i) {
            sum += arr[i];
        }
        return (double)sum / (n - 2 * k);
    }
};
      

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

var trimMean = function(arr, k) {
    arr.sort((a, b) => a - b);
    let trimmed = arr.slice(k, arr.length - k);
    let sum = trimmed.reduce((a, b) => a + b, 0);
    return sum / trimmed.length;
};