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 <= 1000arr.length is a multiple of 20.0 <= arr[i] <= 105Problem Overview: Given an integer array, remove the smallest 5% and largest 5% of elements, then return the mean of the remaining values. The challenge is identifying which elements to discard efficiently and computing the average of the middle portion.
Approach 1: Sorting Approach (Time: O(n log n), Space: O(1) or O(log n))
Sort the array so the smallest and largest elements are grouped at the ends. If the array length is n, remove n / 20 elements from both the beginning and the end (since 5% = 1/20). After sorting, iterate from index k to n - k - 1, accumulate the sum, and divide by the number of remaining elements. Sorting guarantees correct ordering, making it straightforward to slice out the extremes. This approach is simple and reliable when working with moderate input sizes.
The method relies heavily on sorting to structure the data. After sorting, only a single pass is required to compute the sum, which keeps the implementation short and easy to verify during interviews.
Approach 2: Partition Approach Using Quickselect Variation (Time: O(n) average, O(n^2) worst, Space: O(1))
Instead of fully sorting the array, use a partition-based algorithm similar to Quickselect. The idea is to position the k-th smallest element and the (n - k)-th smallest element using repeated partition operations. Once those boundaries are fixed, all elements between them represent the valid middle segment.
This avoids sorting the entire array. Partitioning rearranges elements around a pivot so that values smaller than the pivot move left and larger values move right. By selecting pivots strategically, you isolate the boundaries of the middle 90% region in linear time on average. After that, iterate through the middle section and compute the sum normally. This approach is useful when n is large and you want to avoid the O(n log n) cost of sorting.
The technique is a practical application of selection algorithms related to arrays and partial ordering problems. It demonstrates how partition logic from quicksort can solve order-statistic problems efficiently.
Recommended for interviews: The sorting approach is usually expected first because it is easy to implement and clearly correct. Interviewers often accept it immediately for an easy problem. The partition/Quickselect approach shows deeper algorithmic knowledge and improves the average time complexity to O(n), which is valuable when discussing optimization.
The simplest way to tackle this problem is to first sort the array. Once sorted, it's easy to remove the smallest and largest 5% of the elements. After erasing these entries, compute the mean of the remaining numbers.
This C program sorts the array using qsort, then calculates the number of elements to remove (5% from both ends). It then calculates the sum of the middle elements (those not removed) and computes the mean.
The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) since we are sorting in-place.
Another approach involves modifying partitioning techniques from Quickselect to find and remove the smallest and largest 5% of elements without fully sorting the array. This can reduce the average time complexity in certain scenarios compared to always sorting.
The C solution uses a variation of quickselect to partition the array around the smallest and largest 5% elements. It shifts elements only around the necessary indices and computes the mean of the remaining central segment.
Average time complexity is O(n) for partitioning, though it degrades to O(n^2) in the worst case. Space complexity is O(1), as we modify the array in place.
| Approach | Complexity |
|---|---|
| Sorting Approach | The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) since we are sorting in-place. |
| Partition Approach Using Variation of Quickselect | Average time complexity is O(n) for partitioning, though it degrades to O(n^2) in the worst case. Space complexity is O(1), as we modify the array in place. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) or O(log n) | Best for simple implementation and typical interview constraints |
| Partition (Quickselect Variation) | O(n) average, O(n^2) worst | O(1) | When avoiding full sorting and optimizing for large arrays |
mean of array after removing some elements leetcode | leetcode 1619 | mean | average | array • Naresh Gupta • 1,314 views views
Watch 9 more video solutions →Practice Mean of Array After Removing Some Elements with our built-in code editor and test cases.
Practice on FleetCode