Mean of Array After Removing Some Elements solution and explanation
Google
9 more videos on this problem
mean of array after removing some elements leetcode | leetcode 1619 | mean | average | arrayNaresh Gupta · 3:23 · 1K views
Leetcode | 1619. Mean of Array After Removing Some Elements | Easy | Java SolutionDeveloper Docs · 6:49 · 1K views
LeetCode 1619. Mean of Array After Removing Some Elements - Interview Prep Ep 99Fisher Coder · 4:56 · 747 views
1619. Mean of Array After Removing Some Elements - Python - 1 LineAlgoPrepMaster · 0:59 · 300 views
1619. Mean of Array After Removing Some Elements (Leetcode Easy)Programming Live with Larry · 2:52 · 288 views
Wipro NLTH Coding Questions in Python | 1619. Mean of Array After Removing Some Elements LeeetcodeLet Me Code · 9:38 · 218 views
Mean of Array After Removing Some Elements - LeetCode 1619 - Java Solutionalgobest - Computer Science · 4:10 · 128 views
Leetcode solving: 1619. Mean of Array After Removing Some ElementsMath Geeks · 2:28 · 88 views
LeetCode 1619 | Mean of Array After Removing Some Elements | Array | JavaSleepy Cracker · 2:57 · 31 views
1619. Mean of Array After Removing Some Elements - Javascript - Time: O(n log n) Space: O(1)Aaron Sadino Coding · 8:07 · 15 views
The problem
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.lengthis a multiple of20.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.
def trimMean(arr):
arr.sort()
n = len(arr)
remove_count = n * 5 // 100
return sum(arr[remove_count:n-remove_count]) / (n - 2 * remove_count)
# Example usage
arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
print(f"{trimMean(arr):.5f}")import java.util.Arrays;
public class Main {
public static double trimMean(int[] arr) {
Arrays.sort(arr);
int n = arr.length;
int removeCount = n * 5 / 100;
double sum = 0;
for (int i = removeCount; i < n - removeCount; i++) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
public static void main(String[] args) {
int[] arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
System.out.printf("%.5f\n", trimMean(arr));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
double trimMean(vector<int>& arr) {
sort(arr.begin(), arr.end());
int n = arr.size();
int removeCount = n * 5 / 100;
int sum = 0;
for (int i = removeCount; i < n - removeCount; ++i) {
sum += arr[i];
}
return static_cast<double>(sum) / (n - 2 * removeCount);
}
int main() {
vector<int> arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
cout << fixed << setprecision(5) << trimMean(arr) << endl;
return 0;
}function trimMean(arr) {
arr.sort((a, b) => a - b);
const n = arr.length;
const removeCount = Math.floor(n * 0.05);
let sum = 0;
for (let i = removeCount; i < n - removeCount; i++) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
// Example usage
const arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0];
console.log(trimMean(arr).toFixed(5));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
double trimMean(int* arr, int arrSize) {
qsort(arr, arrSize, sizeof(int), compare);
int removeCount = arrSize * 0.05;
int sum = 0;
for (int i = removeCount; i < arrSize - removeCount; i++) {
sum += arr[i];
}
return (double)sum / (arrSize - 2 * removeCount);
}
int main() {
int arr[] = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%.5f\n", trimMean(arr, arrSize));
return 0;
}using System;
public class Solution {
public double TrimMean(int[] arr) {
Array.Sort(arr);
int n = arr.Length;
int removeCount = n * 5 / 100;
double sum = 0;
for (int i = removeCount; i < n - removeCount; i++) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
public static void Main() {
int[] arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
Console.WriteLine(string.Format("{0:F5}", new Solution().TrimMean(arr)));
}
}This Python function uses the built-in sort() method to sort the array. It then calculates the number of elements to truncate, sums the remainder, and divides by their count to find the mean.
Time complexity is O(n log n) for sorting, and space complexity is O(1) as sorting is in place.
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.
import random
def partition(arr, left, right, pivot_index):
pivot = arr[pivot_index]
arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
store_index = left
for i in range(left, right):
if arr[i] < pivot:
arr[store_index], arr[i] = arr[i], arr[store_index]
store_index += 1
arr[right], arr[store_index] = arr[store_index], arr[right]
return store_index
def quickselect(arr, left, right, k):
if left == right:
return
pivot_index = random.randint(left, right)
pivot_index = partition(arr, left, right, pivot_index)
if k == pivot_index:
return
elif k < pivot_index:
return quickselect(arr, left, pivot_index - 1, k)
else:
return quickselect(arr, pivot_index + 1, right, k)
def trimMean(arr):
n = len(arr)
remove_count = n * 5 // 100
quickselect(arr, 0, n - 1, remove_count)
quickselect(arr, remove_count, n - 1, n - remove_count)
return sum(arr[remove_count:n-remove_count]) / (n - 2 * remove_count)
# Example usage
arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
print(f"{trimMean(arr):.5f}")import java.util.Random;
public class Main {
private static void quickSelect(int[] arr, int left, int right, int k) {
if (left == right) return;
Random random = new Random();
int pivotIndex = left + random.nextInt(right - left + 1);
pivotIndex = partition(arr, left, right, pivotIndex);
if (k == pivotIndex) return;
else if (k < pivotIndex) quickSelect(arr, left, pivotIndex - 1, k);
else quickSelect(arr, pivotIndex + 1, right, k);
}
private static int partition(int[] arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr, storeIndex, i);
storeIndex++;
}
}
swap(arr, right, storeIndex);
return storeIndex;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static double trimMean(int[] arr) {
int n = arr.length;
int removeCount = n * 5 / 100;
quickSelect(arr, 0, n - 1, removeCount);
quickSelect(arr, removeCount, n - 1, n - removeCount);
double sum = 0;
for (int i = removeCount; i < n - removeCount; ++i) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
public static void main(String[] args) {
int[] arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
System.out.printf("%.5f\n", trimMean(arr));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void quickselect(vector<int>& arr, int left, int right, int k) {
if (left == right) return;
int pivotIndex = left + (right - left) / 2;
pivotIndex = partition(arr, left, right, pivotIndex);
if (k == pivotIndex) return;
else if (k < pivotIndex) quickselect(arr, left, pivotIndex - 1, k);
else quickselect(arr, pivotIndex + 1, right, k);
}
int partition(vector<int>& arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr[pivotIndex], arr[right]);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr[storeIndex], arr[i]);
storeIndex++;
}
}
swap(arr[right], arr[storeIndex]);
return storeIndex;
}
double trimMean(vector<int>& arr) {
int n = arr.size();
int removeCount = n * 5 / 100;
quickselect(arr, 0, n - 1, removeCount);
quickselect(arr, removeCount, n - 1, n - removeCount);
double sum = 0;
for (int i = removeCount; i < n - removeCount; ++i) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
int main() {
vector<int> arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
cout << fixed << setprecision(5) << trimMean(arr) << endl;
return 0;
}function partition(arr, left, right, pivotIndex) {
const pivot = arr[pivotIndex];
[arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];
let storeIndex = left;
for (let i = left; i < right; i++) {
if (arr[i] < pivot) {
[arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
storeIndex++;
}
}
[arr[right], arr[storeIndex]] = [arr[storeIndex], arr[right]];
return storeIndex;
}
function quickselect(arr, left, right, k) {
if (left === right) return;
let pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
pivotIndex = partition(arr, left, right, pivotIndex);
if (k === pivotIndex) return;
else if (k < pivotIndex) quickselect(arr, left, pivotIndex - 1, k);
else quickselect(arr, pivotIndex + 1, right, k);
}
function trimMean(arr) {
const n = arr.length;
const removeCount = Math.floor(n * 0.05);
quickselect(arr, 0, n - 1, removeCount);
quickselect(arr, removeCount, n - 1, n - removeCount);
const sum = arr.slice(removeCount, n - removeCount).reduce((a, b) => a + b, 0);
return sum / (n - 2 * removeCount);
}
// Example usage
const arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0];
console.log(trimMean(arr).toFixed(5));#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int* arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[high]);
return i;
}
void quickselect(int* arr, int low, int high, int k) {
if (low < high) {
int pi = partition(arr, low, high);
if (pi == k)
return;
if (pi < k)
quickselect(arr, pi + 1, high, k);
else
quickselect(arr, low, pi - 1, k);
}
}
double trimMean(int* arr, int arrSize) {
int removeCount = arrSize * 0.05;
quickselect(arr, 0, arrSize - 1, removeCount);
quickselect(arr, removeCount, arrSize - 1, arrSize - removeCount);
int sum = 0;
for (int i = removeCount; i < arrSize - removeCount; ++i) {
sum += arr[i];
}
return (double)sum / (arrSize - 2 * removeCount);
}
int main() {
int arr[] = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%.5f\n", trimMean(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private Random rand = new Random();
private int Partition(int[] arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
int temp = arr[pivotIndex];
arr[pivotIndex] = arr[right];
arr[right] = temp;
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
temp = arr[i];
arr[i] = arr[storeIndex];
arr[storeIndex] = temp;
storeIndex++;
}
}
temp = arr[right];
arr[right] = arr[storeIndex];
arr[storeIndex] = temp;
return storeIndex;
}
private void Quickselect(int[] arr, int left, int right, int k) {
if (left == right) return;
int pivotIndex = left + rand.Next(right - left + 1);
pivotIndex = Partition(arr, left, right, pivotIndex);
if (k == pivotIndex) return;
else if (k < pivotIndex) Quickselect(arr, left, pivotIndex - 1, k);
else Quickselect(arr, pivotIndex + 1, right, k);
}
public double TrimMean(int[] arr) {
int n = arr.Length;
int removeCount = n * 5 / 100;
Quickselect(arr, 0, n - 1, removeCount);
Quickselect(arr, removeCount, n - 1, n - removeCount);
double sum = 0;
for (int i = removeCount; i < n - removeCount; i++) {
sum += arr[i];
}
return sum / (n - 2 * removeCount);
}
public static void Main() {
int[] arr = {6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0};
Console.WriteLine(string.Format("{0:F5}", new Solution().TrimMean(arr)));
}
}This Python solution applies the quickselect methodology to efficiently discard the smallest and largest 5% elements, focuses on modifying partitioned segments, and determines the mean value.
Time complexity averages O(n) with proper pivoting, while space remains O(1) for in-place array operations.
Approach 3: Default Approach
function trimMean(arr: number[]): number {
arr.sort((a, b) => a - b);
let n = arr.length,
rmLen = n * 0.05;
let sum = 0;
for (let i = rmLen; i < n - rmLen; i++) {
sum += arr[i];
}
return sum / (n * 0.9);
}func trimMean(arr []int) float64 {
sort.Ints(arr)
n := len(arr)
sum := 0.0
for i := n / 20; i < n-n/20; i++ {
sum += float64(arr[i])
}
return sum / (float64(n) * 0.9)
}impl Solution {
pub fn trim_mean(mut arr: Vec<i32>) -> f64 {
arr.sort();
let n = arr.len();
let count = ((n as f64) * 0.05).floor() as usize;
let mut sum = 0;
for i in count..n - count {
sum += arr[i];
}
(sum as f64) / ((n as f64) * 0.9)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting Approach | Time complexity is O(n log n) for sorting, and space complexity is O(1) as sorting is in place. |
| Partition Approach Using Variation of Quickselect | Time complexity averages O(n) with proper pivoting, while space remains O(1) for in-place array operations. |
| Default Approach | – |
Complexity analysis
| 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 |
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.