LeetCode Solutions Blog

Average Salary Excluding the Minimum and Maximum Salary

Number: 1584

Difficulty: Easy

Paid? No

Problem Description

Given an array of unique integers representing each employee's salary, return the average salary computed from the employees excluding the minimum and maximum salaries.

Key Insights

All salary values are unique, so there is exactly one minimum and one maximum.
Identify and exclude the minimum and maximum salaries.
Compute the sum of the remaining salaries and divide it by their count.

Space and Time Complexity

Time Complexity: O(n), where n is the number of employees (single or double pass over the list). Space Complexity: O(1), as only a few extra variables are used.

Solution

The approach involves first determining the minimum and maximum salaries in the array using a single pass (or built-in methods). Then, by iterating through the array, we sum the values that are not equal to either the minimum or maximum. Finally, the average is computed by dividing the accumulated sum by the count of the salaries taken into account. This method uses constant extra space and efficiently computes the result in linear time.

Code Solutions

# Python solution with line-by-line comments:

def average(salary):
    # Find the minimum salary in the list
    min_salary = min(salary)  # O(n) time.
    # Find the maximum salary in the list
    max_salary = max(salary)  # O(n) time.
    
    total = 0  # Initialize total sum of salaries excluding min and max.
    count = 0  # Initialize count of salaries considered.
    
    # Iterate through each salary in the list.
    for s in salary:
        # Exclude the minimum and maximum salaries.
        if s != min_salary and s != max_salary:
            total += s    # Accumulate the salary.
            count += 1    # Increase the count.
    
    # Compute and return the average salary.
    return total / count

# Test the function with a sample input.
example_salary = [4000, 3000, 1000, 2000]
print(average(example_salary))  # Expected Output: 2500.00000