{x}
blog image

Mean of Array After Removing Some Elements

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

Solution Explanation

The problem asks to calculate the mean of an array after removing the smallest 5% and largest 5% of its elements. The solution involves these steps:

  1. Sorting: The input array arr needs to be sorted in ascending order. This allows easy identification and removal of the smallest and largest elements.

  2. Removing Extremes: After sorting, the smallest 5% and largest 5% of elements are removed. The number of elements to remove from each end is calculated as (len(arr) * 0.05). We use floor() to round it down to nearest integer to get the index. The remaining elements form a subarray for calculation.

  3. Calculating the Mean: The mean (average) of the remaining elements is calculated by summing them and dividing by their count. The count of remaining elements is len(arr) * 0.9.

  4. Rounding (Optional): The problem states that answers within 10^-5 of the actual answer are acceptable. While not strictly required in all cases, the solutions provided often round the final result to 5 decimal places for precision.

Time and Space Complexity Analysis

  • Time Complexity: The dominant operation is sorting the array, which has a time complexity of O(n log n), where n is the length of the array. The other operations (removing elements and calculating the mean) take linear time, O(n). Therefore, the overall time complexity is O(n log n).

  • Space Complexity: In most implementations, the space complexity is O(1) because the sorting is done in-place (or with minimal auxiliary space in some languages). If a copy of the array is explicitly made, the space complexity will become O(n). The space used for storing the sum and other variables is constant regardless of the array size.

Code Explanation (Python as an Example)

The Python solution is concise and demonstrates the key steps effectively:

class Solution:
    def trimMean(self, arr: List[int]) -> float:
        n = len(arr)
        start, end = int(n * 0.05), int(n * 0.95) # Calculate indices to remove 5% from each end.  int() does the floor.
        arr.sort() # Sort the array in place
        t = arr[start:end] # Slice the array to exclude the first and last 5%
        return round(sum(t) / len(t), 5) # Calculate mean and round to 5 decimal places

The other language solutions follow a similar approach, adapting the syntax and data structures as needed for their respective languages. Key differences are mostly in how sorting and array manipulation is handled (e.g., using Arrays.sort() in Java, sort() in C++ and Go's sort.Ints(), etc.). But the underlying algorithm remains the same.