Mean of Array After Removing Some Elements

Difficulty: Easy | Acceptance: 71.80% | Paid: No Topics: Array, Sorting

Given an integer array arr, return the mean of the remaining elements after removing the smallest 5% and the largest 5% of the elements. Answers within 10⁻⁵ of the actual answer will be considered accepted.

• Examples
• Constraints
• Sorting Approach
• Counting Sort Approach

Examples

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 smallest and the largest 5% elements, the array is [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2].

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,9,8,9,2,8,2,8,8,8,1,9] Output: 4.77778 Explanation: After erasing the smallest and the largest 5% elements, the array is [7,7,7,5,7,8,3,4,7,8,1,6,8,1,1,2,9,8,9,2,8,2,8,8,8,1,9].

Input: arr = [9,7,8,7,7,8,4,4,6,8,8,7,5,1,10] Output: 6.66667 Explanation: After erasing the smallest and the largest 5% elements, the array is [9,7,8,7,7,8,4,4,6,8,8,7,5,1,10]. Since 15 * 0.05 = 0.75, we remove 0 elements from the smallest and largest.

Constraints

20 <= arr.length <= 1000
arr.length is a multiple of 20.
1 <= arr[i] <= 10^5

Sorting Approach

Intuition Sorting the array places the elements in ascending order. This allows us to easily identify and exclude the smallest 5% and largest 5% of elements, which will be located at the beginning and end of the sorted array respectively.

Steps

• Sort the array in non-decreasing order.
• Calculate the number of elements to remove, k, which is 5% of the array length.
• Sum the elements from index k to length - k - 1.
• Divide the sum by the number of remaining elements (length - 2 * k) to get the mean.

class Solution:
    def trimMean(self, arr: list[int]) -> float:
        arr.sort()
        n = len(arr)
        k = n // 20
        trimmed_sum = sum(arr[k:n - k])
        return trimmed_sum / (n - 2 * k)

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s memory usage.
• Notes: This is the most straightforward approach and is efficient enough given the constraints (n <= 1000).

Counting Sort Approach

Intuition Since the values in the array are constrained to a relatively small range (1 to 10⁵), we can use a frequency array (Counting Sort) to count occurrences of each number. This allows us to iterate through the value range to remove the smallest and largest elements without sorting the entire array.

Steps

• Create a frequency array of size 100001 initialized to 0.
• Iterate through the input array and populate the frequency counts.
• Calculate k (5% of length).
• Iterate from the smallest value (1) upwards, decrementing the frequency count and k until we have removed k smallest elements.
• Iterate from the largest value (100000) downwards, decrementing the frequency count and k until we have removed k largest elements.
• Iterate through the frequency array again to sum the remaining values and count them.
• Return the sum divided by the count.

class Solution:
    def trimMean(self, arr: list[int]) -> float:
        n = len(arr)
        k = n // 20
        freq = [0] * 100001
        
        for x in arr:
            freq[x] += 1
            
        # Remove smallest k elements
        to_remove = k
        i = 1
        while to_remove > 0:
            if freq[i] > 0:
                freq[i] -= 1
                to_remove -= 1
            else:
                i += 1
                
        # Remove largest k elements
        to_remove = k
        i = 100000
        while to_remove > 0:
            if freq[i] > 0:
                freq[i] -= 1
                to_remove -= 1
            else:
                i -= 1
                
        # Calculate mean of remaining
        total_sum = 0
        count = 0
        for i in range(1, 100001):
            if freq[i] > 0:
                total_sum += i * freq[i]
                count += freq[i]
                
        return total_sum / count

Complexity

• Time: O(n + C), where C is the range of values (100001). This is effectively O(n) since C is constant relative to input constraints.
• Space: O(C) to store the frequency array.
• Notes: This approach avoids the O(n log n) sorting cost, trading it for O(C) space. It is efficient when the range of values is limited.