Domain 1EasyCORE

Average Salary Excluding the Minimum and Maximum Salary

The problem requires calculating the average salary of employees excluding the minimum and maximum salaries from a given array of unique integers representing employee salaries. The input is an array `salary` where each element is a unique integer within the range `[10^3, 10^6]`. The output should be the average of the remaining salaries after removing the smallest and largest values.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Sort

1491. Average Salary Excluding the Minimum and Maximum Salary

Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 68.5%


Problem Breakdown

The problem requires calculating the average salary of employees excluding the minimum and maximum salaries from a given array of unique integers representing employee salaries. The input is an array salary where each element is a unique integer within the range [10^3, 10^6]. The output should be the average of the remaining salaries after removing the smallest and largest values.

Inputs:

  • An array of integers salary with at least 3 elements and at most 100 elements.
  • Each element in the array is a unique integer within the range [10^3, 10^6].

Outputs:

  • A floating-point number representing the average salary excluding the minimum and maximum salaries.

Implicit Constraints or Tricky Edge Cases:

  • The array always has at least three elements, so there will always be at least one salary to consider after removing the min and max.
  • All salaries are unique, which simplifies finding the min and max values.
  • The result should be accurate within 10^-5 of the actual value.

Intuition

A brute-force approach would involve sorting the array, removing the first and last elements (min and max), and then calculating the average. However, this approach has a time complexity of O(n log n) due to the sorting step, which is not optimal given that we only need to find the min and max values.

The key insight is to iterate through the array once to simultaneously find both the minimum and maximum salaries while also calculating the total sum of all salaries. This allows us to compute the average in a single pass with O(n) time complexity.

Approach

  1. Initialize variables total_sum, min_salary, and max_salary to store the cumulative sum, smallest salary, and largest salary respectively.
  2. Iterate through each salary in the array:
    • Add the current salary to total_sum.
    • Update min_salary if the current salary is smaller than the current min_salary.
    • Update max_salary if the current salary is larger than the current max_salary.
  3. Calculate the adjusted total sum by subtracting min_salary and max_salary from total_sum.
  4. Compute the average by dividing the adjusted total sum by the number of remaining salaries (i.e., len(salary) - 2).
  5. Return the computed average.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the salary array. We only make a single pass through the array to find the min, max, and total sum.
  • Space Complexity: O(1), as we are using a constant amount of extra space regardless of the input size.

Solution

def average(salary):
    # Initialize variables to store total sum, minimum salary, and maximum salary
    total_sum = 0
    min_salary = float('inf')
    max_salary = float('-inf')
    
    # Iterate through each salary in the array
    for s in salary:
        total_sum += s
        if s < min_salary:
            min_salary = s
        if s > max_salary:
            max_salary = s
    
    # Calculate adjusted total sum by excluding min and max salaries
    adjusted_total_sum = total_sum - min_salary - max_salary
    
    # Compute the average of remaining salaries
    average_salary = adjusted_total_sum / (len(salary) - 2)
    
    return average_salary

# Example usage:
# print(average([4000,3000,1000,2000]))  # Output: 2500.00000

Edge Cases Handled

  • Minimum and Maximum at Ends: If the minimum salary is the first element and the maximum is the last, or vice versa, the algorithm correctly excludes them.
  • All Salaries Equal Except Two: The unique constraint ensures that there are always distinct min and max values to exclude.
  • Typical Case with Distinct Values: Any typical input where all salaries are distinct will be handled correctly by finding the correct min and max.