LeetCode Problem 1619

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

LeetCode 1619, Mean of Array After Removing Some Elements

Problem Understanding

The problem gives us an integer array arr and asks us to compute the average value after removing the smallest 5% and the largest 5% of the elements.

The important detail is that the removal is based on the sorted order of the array. We are not simply removing one minimum value and one maximum value. Instead, we sort the array and remove the lowest 5% of elements and the highest 5% of elements.

For example, if the array length is 20, then:

• 5% of 20 = 1
• We remove the first 1 element after sorting
• We also remove the last 1 element after sorting

The remaining 18 elements are used to compute the mean.

The input array:

• Contains integers
• Has length between 20 and 1000
• Always has a length that is a multiple of 20

That last constraint is extremely important because it guarantees that 5% of the array size is always an integer. We never need to worry about rounding when determining how many elements to remove.

The expected output is a floating point number representing the arithmetic mean of the remaining elements.

Several edge cases are already handled by the constraints:

• The array is never empty
• At least one element will always be removed from each side because the minimum length is 20
• The percentage removal count is always exact
• Values may repeat many times, so we must remove elements by position after sorting, not by value

A naive implementation could make mistakes by:

• Removing only the minimum and maximum values instead of 5%
• Forgetting to sort the array
• Using integer division when computing the average
• Incorrectly handling duplicate values

Approaches

Brute Force Approach

The brute force idea is to sort the array, explicitly create a new array containing only the middle portion, and then compute the average.

The algorithm works as follows:

1. Sort the array
2. Compute how many elements to remove:

remove_count = len(arr) // 20 3. Create a new sliced array:

trimmed = arr[remove_count : n - remove_count] 4. Compute the sum of the trimmed array 5. Divide by the number of remaining elements

This approach is correct because sorting guarantees the smallest elements appear first and the largest elements appear last.

However, this approach uses additional space because it creates a new sliced array. While the constraints are small enough that this still passes easily, we can optimize the memory usage.

Optimal Approach

The key observation is that we do not actually need to create a separate trimmed array.

After sorting, we already know exactly which indices belong to the valid middle section. We can simply iterate through that range and compute the sum directly.

This avoids allocating an extra array and reduces the auxiliary space complexity.

The steps become:

1. Sort the array
2. Compute how many elements to discard
3. Iterate only through the valid middle range
4. Compute the sum
5. Return the average

The sorting operation dominates the runtime.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Creates a trimmed slice after sorting
Optimal	O(n log n)	O(1) or O(log n)	Sums directly from the sorted array

Algorithm Walkthrough

Optimal Algorithm

1. Sort the array in ascending order.

Sorting is necessary because the problem defines the smallest and largest 5% relative to sorted order. Without sorting, we would not know which elements belong to the extremes. 2. Compute how many elements must be removed.

Since the array length is always a multiple of 20, we can calculate:

remove_count = n // 20

This works because 5% = 1/20. 3. Determine the valid range of indices.

After removing the smallest and largest 5%, the remaining elements lie between:

start = remove_count
end = n - remove_count

The valid indices are [start, end). 4. Compute the sum of the remaining elements.

Iterate through the valid middle range and accumulate the total. 5. Compute the mean.

The number of remaining elements is:

remaining = n - 2 * remove_count

Return:

total / remaining

Why it works

Sorting places all elements in ascending order. Removing the first remove_count elements removes exactly the smallest 5%, and removing the last remove_count elements removes exactly the largest 5%.

Every remaining element belongs to the valid middle section of the sorted array. Since the arithmetic mean is simply the sum divided by the number of elements, computing the average of this middle section produces the correct answer.

Python Solution

from typing import List

class Solution:
    def trimMean(self, arr: List[int]) -> float:
        arr.sort()

        n = len(arr)
        remove_count = n // 20

        total = 0

        for i in range(remove_count, n - remove_count):
            total += arr[i]

        remaining_count = n - 2 * remove_count

        return total / remaining_count

The implementation begins by sorting the array in ascending order. This is the most important preprocessing step because the problem requires removing the smallest and largest portions of the array.

Next, the code calculates remove_count, which represents how many elements correspond to 5% of the array length.

Instead of creating a separate trimmed array, the solution iterates directly through the valid middle indices. During this loop, it accumulates the sum into total.

Finally, the code computes how many elements remain after both removals and divides the sum by that count to produce the mean.

The implementation uses floating point division automatically in Python because the / operator returns a float.

Go Solution

package main

import "sort"

func trimMean(arr []int) float64 {
	sort.Ints(arr)

	n := len(arr)
	removeCount := n / 20

	total := 0

	for i := removeCount; i < n-removeCount; i++ {
		total += arr[i]
	}

	remainingCount := n - 2*removeCount

	return float64(total) / float64(remainingCount)
}

The Go solution follows the exact same algorithmic structure as the Python version.

One important difference is that Go requires explicit conversion to float64 before division. If we divided two integers directly, Go would perform integer division and lose the fractional component.

The array is sorted in place using sort.Ints.

Go slices are reference-like structures, so sorting modifies the original slice directly without additional copying.

Worked Examples

Example 1

Input:

[1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]

Step 1: Sort the array

The array is already sorted.

Index	Value
0	1
1-18	2
19	3

Step 2: Compute removal count

n = 20
remove_count = 20 // 20 = 1

Remove:

• First 1 element
• Last 1 element

Step 3: Remaining elements

Remaining indices:

1 through 18

All remaining values are:

2

Step 4: Compute sum

sum = 18 * 2 = 36

Step 5: Compute mean

36 / 18 = 2.0

Output:

2.00000

Example 2

Input:

[6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]

Step 1: Sort the array

[0,0,0,0,1,2,2,2,3,5,5,5,5,6,6,7,7,8,8,10]

Step 2: Compute removal count

n = 20
remove_count = 1

Remove:

• First element: 0
• Last element: 10

Step 3: Remaining array

[0,0,0,1,2,2,2,3,5,5,5,5,6,6,7,7,8,8]

Step 4: Compute sum

0+0+0+1+2+2+2+3+5+5+5+5+6+6+7+7+8+8 = 72

Step 5: Compute mean

72 / 18 = 4.0

Output:

4.00000

Example 3

Input:

[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]

Step 1: Sort the array

[0,0,0,0,1,1,1,1,1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,8,8,8,8,8,8,8,9,10,10]

Step 2: Compute removal count

n = 40
remove_count = 2

Remove:

• First 2 elements
• Last 2 elements

Step 3: Compute remaining sum

The remaining middle section sums to:

172

Step 4: Remaining count

40 - 4 = 36

Step 5: Compute mean

172 / 36 = 4.77778

Output:

4.77778

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Only a few variables are used beyond sorting overhead

The dominant operation is sorting the array, which requires O(n log n) time.

After sorting, the summation loop runs in linear time, O(n), but this is smaller than the sorting cost.

The algorithm itself only uses a few integer variables, so the auxiliary space usage is constant. Depending on the language's sorting implementation, there may be additional recursion stack space.

Test Cases

from typing import List

class Solution:
    def trimMean(self, arr: List[int]) -> float:
        arr.sort()

        n = len(arr)
        remove_count = n // 20

        total = 0

        for i in range(remove_count, n - remove_count):
            total += arr[i]

        remaining_count = n - 2 * remove_count

        return total / remaining_count

sol = Solution()

# Example 1 from problem statement
assert abs(sol.trimMean(
    [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
) - 2.0) < 1e-5

# Example 2 from problem statement
assert abs(sol.trimMean(
    [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
) - 4.0) < 1e-5

# Example 3 from problem statement
assert abs(sol.trimMean(
    [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]
) - 4.77778) < 1e-5

# Minimum allowed array size
assert abs(sol.trimMean(
    [0] * 18 + [100, 200]
) - (100 / 18)) < 1e-5

# All elements equal
assert abs(sol.trimMean(
    [5] * 20
) - 5.0) < 1e-5

# Increasing sequence
assert abs(sol.trimMean(
    list(range(20))
) - 9.5) < 1e-5

# Large repeated values
assert abs(sol.trimMean(
    [100000] * 40
) - 100000.0) < 1e-5

# Duplicates near boundaries
assert abs(sol.trimMean(
    [1,1,1,1] + [5] * 32 + [9,9,9,9]
) - 5.0) < 1e-5

Test Case Summary

Test	Why
Example 1	Verifies basic correctness
Example 2	Verifies mixed unsorted values
Example 3	Verifies larger input and fractional mean
Minimum allowed size	Tests smallest valid array length
All elements equal	Ensures trimming does not affect mean
Increasing sequence	Verifies correct index trimming
Large repeated values	Tests upper value range
Duplicates near boundaries	Ensures removal is positional after sorting

Edge Cases

One important edge case is the minimum array length of 20. Since 5% of 20 = 1, the algorithm removes exactly one element from each side. A buggy implementation might accidentally remove zero elements because of incorrect percentage handling or integer rounding. Using n // 20 guarantees the correct count.

Another important edge case involves duplicate values. For example, the smallest value may appear many times. The problem does not ask us to remove all occurrences of the minimum or maximum values. It only asks us to remove the smallest and largest 5% of elements after sorting. The implementation handles this correctly because it trims by index range rather than by value comparison.

A third edge case occurs when all elements are identical. In that situation, removing the smallest and largest 5% still leaves the same value everywhere. Some implementations might accidentally divide by zero or incorrectly handle boundaries. Our implementation always leaves at least 90% of the array intact, so the denominator is always positive.

Another subtle edge case involves integer division during mean calculation. In languages like Go, dividing two integers performs integer division. Without converting to float64, the decimal portion would be lost. The Go implementation explicitly converts both operands before division to ensure the correct floating point result.