Given an array of unique integers salary where salary[i] is the salary of the employee i. Return the average salary of employees excluding the minimum and maximum salary.

Example 1:
Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500

Example 2:
Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000)/1= 2000

Example 3:
Input: salary = [6000,5000,4000,3000,2000,1000]
Output: 3500.00000

Example 4:
Input: salary = [8000,9000,2000,3000,6000,1000]
Output: 4750.00000

Constraints:
3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] is unique.
Answers within 10^-5 of the actual value will be accepted as correct.

Hint:
Get the total sum and subtract the minimum and maximum value in the array. Finally divide the result by n – 2.

Modern C++ Function to compute the Average Excluding the Minimum and Maximum

The traditional implementation is usually based on a loop, that will store the maximum, minimum, and the sum of the array. But in modern C++, you don’t need to do a loop. Instead, you can accomplish these tasks using min_element, max_element, and the std::accumulate function.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    double average(vector<int>& salary) {
        double m1 = *min_element(begin(salary), end(salary));
        double m2 = *max_element(begin(salary), end(salary));
        double sum = std::accumulate(begin(salary), end(salary), 0, [](auto &a, auto &b) {
            return a + b;
        });
        return (sum - m1 - m2) / (salary.size() - 2);
    }
};

class Solution {
public:
    double average(vector<int>& salary) {
        double m1 = *min_element(begin(salary), end(salary));
        double m2 = *max_element(begin(salary), end(salary));
        double sum = std::accumulate(begin(salary), end(salary), 0, [](auto &a, auto &b) {
            return a + b;
        });
        return (sum - m1 - m2) / (salary.size() - 2);
    }
};

Even better, you can use the minmax_element to retrive the min and max value with one pass:

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    double average(vector<int>& salary) {
        auto x = minmax_element(begin(salary), end(salary));
        double sum = std::accumulate(begin(salary), end(salary), 0, [](auto &a, auto &b) {
            return a + b;
        });
        return (sum - *x.first - *x.second) / (salary.size() - 2);
    }
};

class Solution {
public:
    double average(vector<int>& salary) {
        auto x = minmax_element(begin(salary), end(salary));
        double sum = std::accumulate(begin(salary), end(salary), 0, [](auto &a, auto &b) {
            return a + b;
        });
        return (sum - *x.first - *x.second) / (salary.size() - 2);
    }
};

Python Function to Compute the Average Excluding the Minimum and Maximum

In Python, the code is concise:

1
2
3
4
5

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

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

All above implementations have complexity at O(N) time and O(1) space.

–EOF (The Ultimate Computing & Technology Blog) —