Watch 10 video solutions for Mean of Array After Removing Some Elements, a easy level problem involving Array, Sorting. This walkthrough by Naresh Gupta has 1,314 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |