Problem Description

You are given an array of unique integers representing employee salaries. Each element salary[i] represents the salary of the i-th employee.

Your task is to calculate the average salary of all employees after excluding both the minimum and maximum salaries from the calculation.

For example, if you have salaries [4000, 3000, 1000, 2000], you would:

• Identify the minimum salary: 1000
• Identify the maximum salary: 4000
• Calculate the average of the remaining salaries: (3000 + 2000) / 2 = 2500

The solution computes this by:

1. Finding the sum of all salaries using sum(salary)
2. Subtracting the minimum salary using min(salary)
3. Subtracting the maximum salary using max(salary)
4. Dividing the result by len(salary) - 2 (since we removed 2 salaries)

The formula used is: (total_sum - min_salary - max_salary) / (n - 2) where n is the total number of employees.

Note that answers within 10^-5 of the actual answer will be accepted, meaning small floating-point differences are acceptable.

Intuition

When we need to find an average while excluding certain values, the straightforward approach would be to remove those values from our dataset and then calculate the average of what remains. However, there's a more efficient way to think about this problem.

Instead of creating a new array without the minimum and maximum values, we can work with the mathematical property of averages. The average is simply the sum divided by the count. Since we want to exclude the minimum and maximum values, we need:

• The sum without these two values
• The count without these two values

The key insight is that we can calculate the sum of the remaining elements by taking the total sum and subtracting the unwanted values. This is more efficient than filtering the array and then summing, as it requires only one pass through the array to get all three values: sum(), min(), and max().

Think of it like calculating the average score of a class after removing the highest and lowest scores. Rather than rewriting the list of scores, you can simply:

1. Add up all the scores
2. Find and subtract the highest score
3. Find and subtract the lowest score
4. Divide by the new count (original count minus 2)

This gives us the formula: average = (sum - min - max) / (n - 2)

This approach is elegant because it accomplishes the task in O(n) time with only a single conceptual pass through the data (even though sum(), min(), and max() each traverse the array, they're all linear operations), and it uses O(1) extra space since we're not creating any new data structures.

Learn more about Sorting patterns.

Solution Approach

The solution follows a direct simulation approach as described in the reference. We implement the mathematical formula derived from our intuition to calculate the average after excluding extremes.

Implementation Steps:

1. Calculate the total sum: Use Python's built-in sum() function to get the sum of all salaries in the array.

2. Find and subtract the minimum: Use min() to find the smallest salary and subtract it from the total sum.

3. Find and subtract the maximum: Use max() to find the largest salary and subtract it from the remaining sum.

4. Calculate the average: Divide the adjusted sum by len(salary) - 2 since we've removed two elements (the minimum and maximum).

The implementation in a single line:

s = sum(salary) - min(salary) - max(salary)
return s / (len(salary) - 2)

Why this works:

• Since all salaries are unique (as stated in the problem), we don't need to worry about edge cases where multiple employees have the same minimum or maximum salary.
• The mathematical operation (sum - min - max) / (n - 2) gives us exactly what we need: the average of all elements except the extremes.

Time and Space Complexity:

• Time: O(n) where n is the number of employees, as we need to traverse the array to find sum, min, and max
• Space: O(1) as we only use a constant amount of extra space to store the intermediate sum

This simulation approach is optimal for this problem because it's both intuitive and efficient, avoiding unnecessary array manipulations while directly computing the desired result.

Example Walkthrough

Let's walk through a concrete example with the salary array [8000, 9000, 2000, 3000, 6000, 1000].

Step 1: Calculate the total sum

• sum(salary) = 8000 + 9000 + 2000 + 3000 + 6000 + 1000 = 29000

Step 2: Find the minimum salary

• Looking through the array: 8000, 9000, 2000, 3000, 6000, 1000
• min(salary) = 1000

Step 3: Find the maximum salary

• Looking through the same array: 8000, 9000, 2000, 3000, 6000, 1000
• max(salary) = 9000

Step 4: Apply the formula

• Adjusted sum = 29000 - 1000 - 9000 = 19000
• Number of remaining employees = 6 - 2 = 4
• Average = 19000 / 4 = 4750.0

Verification: If we manually exclude 1000 and 9000, we're left with [8000, 2000, 3000, 6000]. The average of these four values is (8000 + 2000 + 3000 + 6000) / 4 = 19000 / 4 = 4750.0 ✓

This confirms our formula works correctly. By using (sum - min - max) / (n - 2), we efficiently computed the average salary excluding the extremes without creating a new filtered array.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array salary. This is because:

• sum(salary) iterates through all n elements once: O(n)
• min(salary) iterates through all n elements once: O(n)
• max(salary) iterates through all n elements once: O(n)
• The subtraction and division operations are constant time: O(1)
• Total: O(n) + O(n) + O(n) + O(1) = O(n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store:

• The variable s for the sum
• The temporary values for min(salary) and max(salary)
• These variables do not scale with the input size

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

Common Pitfalls

1. Multiple Traversals Inefficiency

The current solution makes three separate passes through the array (sum(), min(), and max()), which while still O(n), performs unnecessary repeated iterations.

Better Approach: Calculate all three values in a single pass:

def average(self, salary: List[int]) -> float:
    total_sum = 0
    min_sal = float('inf')
    max_sal = float('-inf')
  
    for sal in salary:
        total_sum += sal
        min_sal = min(min_sal, sal)
        max_sal = max(max_sal, sal)
  
    return (total_sum - min_sal - max_sal) / (len(salary) - 2)

2. Integer Division Error (Language-Specific)

In languages like Python 2 or C++, using integer division could truncate the result:

# Wrong in Python 2 or similar languages
result = (total_sum - min_sal - max_sal) / (len(salary) - 2)  # May truncate

# Correct approach for integer division languages
result = float(total_sum - min_sal - max_sal) / (len(salary) - 2)

3. Edge Case: Small Arrays

While the problem likely guarantees at least 3 elements, not validating this could cause division by zero:

def average(self, salary: List[int]) -> float:
    if len(salary) < 3:
        # Handle edge case appropriately
        return 0.0  # or raise an exception
  
    total_sum = sum(salary) - min(salary) - max(salary)
    return total_sum / (len(salary) - 2)

4. Floating Point Precision Issues

For very large salary values, floating-point arithmetic might introduce precision errors. While the problem accepts answers within 10^-5, be aware of potential precision loss:

# For extreme precision requirements, consider using Decimal
from decimal import Decimal

def average(self, salary: List[int]) -> float:
    salary_decimals = [Decimal(s) for s in salary]
    total = sum(salary_decimals) - min(salary_decimals) - max(salary_decimals)
    return float(total / (len(salary) - 2))

5. Assuming Unique Values

While the problem states salaries are unique, if this constraint were removed, the logic would still work correctly. However, developers might incorrectly try to handle duplicate min/max values specially, which isn't necessary:

# Unnecessary complication (DON'T DO THIS):
if salary.count(min(salary)) > 1:  # This is unnecessary
    # Special handling...
  
# The original approach works fine even with duplicates