Skip to main content
Talentd

Mean of Array After Removing Some Elements - Solution & Explanation

EasyArraySorting14 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Sorting Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Partition Approach Using Variation of Quickselect

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
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ā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SortingO(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) worstO(1)When avoiding full sorting and optimizing for large arrays

Video Solution

mean of array after removing some elements leetcode | leetcode 1619 | mean | average | array ā€¢ Naresh Gupta ā€¢ 1,317 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Mean of Array After Removing Some Elements easy or hard?
The problem is classified as Easy on LeetCode. The core idea is straightforward once you recognize that removing 5% from both ends becomes trivial after sorting the array.
Mean of Array After Removing Some Elements Python/Java solution
In Python or Java, the common implementation sorts the array, computes k = n // 20, and sums elements from index k to n - k - 1. The result is divided by (n - 2k) to get the mean. The same logic translates directly to C++, JavaScript, and other languages.
How to solve Mean of Array After Removing Some Elements in O(n)?
Use a partition-based selection algorithm similar to Quickselect. Find the k-th smallest and (nāˆ’k)-th smallest elements where k = n/20, which represent the boundaries after removing 5% from each side. Once the array is partitioned around these values, iterate through the middle section and compute the mean in linear time.
What is the best approach for Mean of Array After Removing Some Elements?
The most practical approach is sorting the array and removing the smallest and largest 5% of elements. After sorting, compute the sum of the middle section and divide by the remaining count. This solution runs in O(n log n) time and is easy to implement, which makes it common in interviews and production code.
Is Mean of Array After Removing Some Elements asked at Google/Amazon/Meta?
Problems involving trimmed averages and removing extreme values appear in interviews at companies like Amazon and Google because they test array manipulation and understanding of sorting or selection algorithms. While this exact question may vary, the pattern of discarding outliers and computing aggregates is common.
What data structure is used in Mean of Array After Removing Some Elements?
The problem primarily uses arrays. Algorithms applied to the array include sorting and partition-based selection (Quickselect). No additional complex data structures are required beyond variables for summation and index tracking.
What is the time complexity of Mean of Array After Removing Some Elements?
The typical solution uses sorting, which takes O(n log n) time. After sorting, calculating the sum of the remaining elements takes O(n). A more optimized approach uses a Quickselect-style partition algorithm to isolate the boundaries in O(n) average time.

Ready to solve this problem?

Practice Mean of Array After Removing Some Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays