Problem Description

The Leetcode problem "Average Salary Excluding the Minimum and Maximum Salary" asks you to calculate the average salary from a list of salaries, but excluding the minimum and maximum salary values.

Given an array called salary, where each element is a positive integer representing an employee's salary, you should:

• Remove exactly one occurrence of the minimum salary value and one occurrence of the maximum salary value from the array.
• Calculate the average of the remaining salaries.
• Return this average as a floating-point number.

• The array salary contains at least 3 elements.
• All salary values are positive integers.
• There is always exactly one minimum and one maximum value in the input.

Thought Process

To solve this problem, let's first consider the most direct approach:

• We need to remove the lowest and highest salary from the array, then compute the average of the remaining values.
• One naive method is to sort the array, remove the first and last elements, and then compute the average. However, sorting is unnecessary since we only need the min and max values, not the order of the rest.
• Instead, we can scan through the array once to find the minimum and maximum values, as well as the total sum. After the scan, subtract both min and max from the total sum, and divide by the count of the remaining salaries.

Solution Approach

Let's break down the efficient solution step by step:

1. Initialize variables: Set up variables to track the total sum, minimum, and maximum salary values. You can initialize min and max to the first element of the array.
2. Iterate through the array: For each salary:
   • Add it to the running sum.
   • Update min if the current salary is lower than the current min.
   • Update max if the current salary is higher than the current max.
3. Remove min and max: After the loop, subtract min and max from the sum to get the sum of the remaining salaries.
4. Calculate the average: The number of remaining salaries is len(salary) - 2. Divide the adjusted sum by this number to get the average.
5. Return the result: Return the result as a floating-point number.

This approach is optimal because it only requires a single pass through the array (O(n) time), and uses constant extra space.

Example Walkthrough

Let's work through an example to see how the solution unfolds:

Input: salary = [4000, 3000, 1000, 2000]

• First, find the minimum and maximum:
  • Minimum: 1000
  • Maximum: 4000
• Sum all the salaries:
  • 4000 + 3000 + 1000 + 2000 = 10000
• Subtract min and max from the sum:
  • 10000 - 1000 - 4000 = 5000
• Number of remaining salaries: 4 - 2 = 2
• Calculate the average: 5000 / 2 = 2500.0

Code Implementation

class Solution:
    def average(self, salary: List[int]) -> float:
        total = sum(salary)
        min_salary = min(salary)
        max_salary = max(salary)
        return (total - min_salary - max_salary) / (len(salary) - 2)
      

class Solution {
   public:
    double average(vector<int>& salary) {
        int total = 0, min_salary = salary[0], max_salary = salary[0];
        for (int s : salary) {
            total += s;
            if (s < min_salary) min_salary = s;
            if (s > max_salary) max_salary = s;
        }
        return (total - min_salary - max_salary) / double(salary.size() - 2);
    }
};
      

class Solution {
    public double average(int[] salary) {
        int total = 0, min_salary = salary[0], max_salary = salary[0];
        for (int s : salary) {
            total += s;
            if (s < min_salary) min_salary = s;
            if (s > max_salary) max_salary = s;
        }
        return (total - min_salary - max_salary) / (double)(salary.length - 2);
    }
}
      

var average = function(salary) {
    let total = 0, min_salary = salary[0], max_salary = salary[0];
    for (let s of salary) {
        total += s;
        if (s < min_salary) min_salary = s;
        if (s > max_salary) max_salary = s;
    }
    return (total - min_salary - max_salary) / (salary.length - 2);
};
      

Time and Space Complexity

Brute-force Approach:

• If you sort the array and remove the first and last elements, sorting takes O(n log n) time and O(n) space (if making a copy).

• We only need a single pass to find the sum, min, and max, so the time complexity is O(n), where n is the number of salaries.
• Space complexity is O(1) since we use only a few variables for tracking.

Summary

The key insight for this problem is that you don't need to sort or create extra arrays to exclude the minimum and maximum salaries. By tracking the total sum, minimum, and maximum in a single pass, you can efficiently compute the required average in O(n) time and O(1) space. This approach is both simple and optimal, making it a great example of how a little analysis can lead to elegant code.