Problem Description

You are given an integer array arr. Your task is to calculate the mean (average) of the array after removing the smallest 5% and the largest 5% of elements.

The process works as follows:

1. Sort the array in ascending order
2. Remove the bottom 5% of elements (the smallest values)
3. Remove the top 5% of elements (the largest values)
4. Calculate the mean of the remaining 90% of elements

For example, if the array has 20 elements:

• Remove the smallest 5% → remove 1 element from the beginning (0.05 × 20 = 1)
• Remove the largest 5% → remove 1 element from the end
• Calculate the mean of the remaining 18 elements

The solution approach:

1. First, sort the array to arrange elements in ascending order
2. Calculate the starting index as int(n * 0.05) where n is the array length
3. Calculate the ending index as int(n * 0.95)
4. Extract the subarray from start to end index (this excludes the smallest and largest 5%)
5. Calculate the sum of this subarray and divide by its length to get the mean
6. Round the result to 5 decimal places

The answer will be accepted if it's within 10^-5 of the actual answer, meaning your result should be accurate to at least 5 decimal places.

Intuition

The key insight is that to remove the extreme values (smallest 5% and largest 5%), we need to identify which elements fall into these categories. The most straightforward way to do this is by sorting the array first.

Once sorted, the smallest 5% will be at the beginning of the array, and the largest 5% will be at the end. This makes removal trivial - we just need to figure out how many elements constitute 5% of the total.

For an array of length n, exactly n * 0.05 elements make up 5%. Since we might get a decimal value (e.g., 5% of 30 is 1.5), we use int() to truncate to the nearest integer. This gives us the number of elements to exclude from each end.

After determining the cutoff points:

• Start index: int(n * 0.05) - this skips the smallest 5%
• End index: int(n * 0.95) - this stops before the largest 5%

The middle 90% of elements (from index start to end-1) represents our trimmed dataset. We can then simply calculate the arithmetic mean of these remaining elements by summing them and dividing by their count.

The rounding to 5 decimal places ensures our answer meets the precision requirement specified in the problem (within 10^-5 of the actual answer).

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward approach using sorting and array slicing:

1. Get array length: Store n = len(arr) to calculate the trim percentages.

2. Calculate trim indices:

   • start = int(n * 0.05) gives us the index where the trimmed array should begin (excluding the smallest 5%)
   • end = int(n * 0.95) gives us the index where the trimmed array should end (excluding the largest 5%)
   • Using int() ensures we get whole number indices by truncating any decimal values

3. Sort the array: Call arr.sort() to arrange all elements in ascending order. This positions:

   • The smallest 5% at indices [0, start)
   • The middle 90% at indices [start, end)
   • The largest 5% at indices [end, n)

4. Extract the trimmed portion: Use Python's array slicing t = arr[start:end] to get only the middle 90% of elements. This slice operation creates a new list containing elements from index start (inclusive) to index end (exclusive).

5. Calculate and return the mean:

   • sum(t) computes the sum of all elements in the trimmed array
   • len(t) gives the count of elements in the trimmed array
   • sum(t) / len(t) calculates the arithmetic mean
   • round(..., 5) rounds the result to 5 decimal places to meet the precision requirement

The time complexity is O(n log n) due to sorting, and the space complexity is O(n) for storing the trimmed array slice.

Example Walkthrough

Let's walk through a concrete example with a small array to illustrate the solution approach.

Example: arr = [6, 2, 7, 5, 1, 2, 0, 3, 10, 2, 5, 0, 5, 5, 0, 8, 7, 6, 8, 0]

Step 1: Get array length

• n = 20

Step 2: Calculate trim indices

• Bottom 5%: start = int(20 * 0.05) = int(1.0) = 1
• Top 5%: end = int(20 * 0.95) = int(19.0) = 19
• This means we'll remove 1 element from the beginning and 1 element from the end

Step 3: Sort the array

• After sorting: [0, 0, 0, 0, 1, 2, 2, 2, 3, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 10]
• The smallest value (first 0) will be removed
• The largest value (10) will be removed

Step 4: Extract the trimmed portion

• t = arr[1:19] gives us: [0, 0, 0, 1, 2, 2, 2, 3, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8]
• We've excluded:
  • Smallest 5% (index 0): the value 0
  • Largest 5% (index 19): the value 10

Step 5: Calculate the mean

• Sum of trimmed array: 0+0+0+1+2+2+2+3+5+5+5+5+6+6+7+7+8+8 = 76
• Count of elements: 18
• Mean: 76 / 18 = 4.222222...
• Rounded to 5 decimal places: 4.22222

The final answer is 4.22222, which represents the mean of the middle 90% of the data after removing the extreme values.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

• The dominant operation is arr.sort() which uses Timsort (Python's default sorting algorithm) with time complexity O(n log n) where n is the length of the input array
• Computing start and end indices takes O(1) time
• Array slicing arr[start:end] takes O(n) time to create a new list
• Computing the sum of the trimmed array takes O(n) time
• Division and rounding operations take O(1) time
• Overall: O(n log n) + O(n) + O(n) + O(1) = O(n log n)

Space Complexity: O(n)

• The sorting operation in Python creates a copy of the array internally, requiring O(n) auxiliary space
• The sliced array t = arr[start:end] creates a new list containing approximately 0.9n elements, which is O(n) space
• Variables start, end, and n use O(1) space
• Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division vs Float Division

One common mistake is forgetting that the mean calculation requires float division. In older Python versions (Python 2.x) or some other languages, dividing two integers might result in integer division, truncating the decimal part.

Incorrect approach:

# In some contexts, this might perform integer division
mean = sum(trimmed_array) // len(trimmed_array)  # Wrong: uses floor division

Correct approach:

# Ensure float division
mean = sum(trimmed_array) / len(trimmed_array)  # Correct: uses true division
# Or explicitly convert to float
mean = float(sum(trimmed_array)) / len(trimmed_array)

2. Rounding vs Truncating When Calculating Indices

Using round() instead of int() for index calculation can lead to incorrect trimming boundaries, especially when the 5% calculation results in values like 0.5.

Incorrect approach:

trim_start_index = round(n * 0.05)  # Could round up when we want to round down
trim_end_index = round(n * 0.95)    # Could cause off-by-one errors

Correct approach:

trim_start_index = int(n * 0.05)  # Always truncates (rounds down)
trim_end_index = int(n * 0.95)    # Consistent behavior

3. Modifying Original Array

The sort() method modifies the array in-place, which might cause issues if the original array order needs to be preserved elsewhere.

Problematic if original order matters:

arr.sort()  # Modifies the original array

Alternative if preservation needed:

sorted_arr = sorted(arr)  # Creates a new sorted array
trimmed_array = sorted_arr[trim_start_index:trim_end_index]

4. Edge Cases with Small Arrays

When the array size is very small (e.g., less than 20 elements), calculating 5% might result in 0 elements to trim, which could lead to unexpected behavior if not handled properly.

Example issue:

# If n = 10: int(10 * 0.05) = int(0.5) = 0
# This means no elements are trimmed from the start
# If n = 19: int(19 * 0.05) = int(0.95) = 0, int(19 * 0.95) = int(18.05) = 18
# Only 1 element gets trimmed from the end

Solution consideration: The problem statement should guarantee minimum array size, or you should verify that the trimming logic handles these cases appropriately. The current implementation handles this correctly by using int() which truncates to 0 for small arrays.

5. Precision Loss in Final Rounding

Not rounding to the specified precision or using incorrect rounding methods can cause the answer to fail the accuracy requirement.

Incorrect approaches:

return trimmed_mean  # No rounding at all
return int(trimmed_mean * 100000) / 100000  # Manual truncation, not rounding
return round(trimmed_mean)  # Rounds to nearest integer, not 5 decimal places

Correct approach:

return round(trimmed_mean, 5)  # Properly rounds to 5 decimal places