Skip to main content
CodePeet

Average Salary Excluding the Minimum and Maximum Salary

Try it yourself
EasyProblemExternal link

Description

You are given an array salary of distinct whole numbers, where salary[i] is the salary of employee i.

Return the average salary, leaving out the employee with the lowest salary and the employee with the highest salary. Answers within 10^-5 of the exact average are accepted.

Examples

Example 1

Input: salary = [5000, 3000, 8000, 4000]

Output: 4500.00000

Explanation: The lowest salary is 3000 and the highest is 8000. The two left are 5000 and 4000, and (5000 + 4000) / 2 = 4500.

Example 2

Input: salary = [1000, 2000, 3000]

Output: 2000.00000

Explanation: Leaving out 1000 and 3000 leaves a single salary, 2000, which is its own average.

Example 3

Input: salary = [6000, 1000, 7000, 2000, 5000]

Output: 4333.33333

Explanation: Leaving out 1000 and 7000 leaves 6000, 2000 and 5000. (6000 + 2000 + 5000) / 3 = 13000 / 3 = 4333.333…, which is not a whole number.

Constraints

  • 3 ≤ salary.length ≤ 100
  • 1000 ≤ salary[i] ≤ 10^6
  • All the numbers in salary are different.

Editorial

Brute Force

Intuition

Sort, then drop both ends. Once the salaries are sorted from lowest to highest, the minimum is the first one and the maximum is the last one. Leave those two out and average the rest: add up the middle salaries and divide by how many there are, n − 2. Because the salaries are all different, there is exactly one lowest and one highest to leave out.

The salaries 6000, 1000, 7000, 2000 and 5000 as bars, then sorted into 1000, 2000, 5000, 6000 and 7000 with the two ends, 1000 and 7000, dropped and the middle three averaged: (2000 + 5000 + 6000) ÷ 3 = 4333.33333.

Sort a copy. Sorting the array itself would change the caller's data, a side effect nobody asked for. sorted(salary) in Python already returns a new list; in C++ and Java the code copies the array before sorting it.

Divide as decimals. The answer is often not a whole number: Example 3 gives 13000 / 3 = 4333.333…. In C++ and Java, dividing one whole number by another throws the fraction away and gives 4333, which is wrong by far more than the 10^-5 allowed. Turning the total into a double before dividing keeps the fraction. In Python 3, / always divides as decimals; // is the one that drops the fraction.

Step-by-Step Explanation

We trace Example 3, salary = [6000, 1000, 7000, 2000, 5000]. The two ends that are left out are orange, and the salaries added to the total are green.

Step 1: The salaries as given: 6000, 1000, 7000, 2000, 5000.

Step 2: Sort a copy: 1000, 2000, 5000, 6000, 7000. The ends, 1000 and 7000, are left out.

Step 3: Add 2000: total = 2000.

Step 4: Add 5000: total = 7000.

Step 5: Add 6000: total = 13000.

Step 6: Return 13000 / 3 = 4333.33333.

Brute Force — Sort, Drop Both Ends, Average the Middle — Example 3: the salaries are sorted, the two ends are left out, and the middle is added up and divided.

Algorithm

  1. Make a sorted copy ordered of salary.
  2. Add up ordered[1] through ordered[n − 2], leaving out the first and the last.
  3. Return that total divided by n − 2, as a decimal.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    double average(vector<int>& salary) {
        vector<int> ordered = salary;  // sort a copy, so the caller's vector keeps its order
        sort(ordered.begin(), ordered.end());
        long long total = 0;
        for (int i = 1; i + 1 < (int)ordered.size(); i++) total += ordered[i];  // skip the lowest and the highest
        return (double)total / (ordered.size() - 2);  // the cast makes this a decimal division
    }
};
class Solution:
    def average(self, salary: list[int]) -> float:
        ordered = sorted(salary)  # a sorted copy; the caller's list keeps its order
        middle = ordered[1:-1]    # without the lowest and the highest
        return sum(middle) / len(middle)
import java.util.Arrays;

class Solution {
    public double average(int[] salary) {
        int[] ordered = salary.clone();  // sort a copy, so the caller's array keeps its order
        Arrays.sort(ordered);
        long total = 0;
        for (int i = 1; i + 1 < ordered.length; i++) total += ordered[i];  // skip the lowest and the highest
        return (double) total / (ordered.length - 2);  // the cast makes this a decimal division
    }
}

Complexity Analysis

Time Complexity: O(n log n) for the sort; the sum afterwards is O(n).

Space Complexity: O(n) for the sorted copy.

Why This Approach Is Not Efficient

Sorting puts every salary in its place, but the answer needs only three facts: the total, the lowest and the highest. The order of the salaries in between is never used, and sorting is the most expensive step, O(n log n) against O(n) for reading the array once. It also needs a full copy of the array.

At this problem's size the difference cannot be seen, and in Python the sort is even a little faster. Measured at n = 100, it takes 2.2 microseconds, against 3.6 for the one-pass loop below, because sorted and sum run as compiled code while a loop runs line by line. The cost of sorting shows as the input grows: for a million salaries, 0.131 s against 0.040 s.

Optimal Approach - One Pass for the Total, the Lowest and the Highest

Intuition

The middle sum without sorting. The salaries in the middle add up to the total of all the salaries minus the lowest minus the highest. None of the three needs the salaries in order, and all three can be kept up to date while reading the array once:

  • total adds each salary;
  • lowest keeps the smallest salary seen so far;
  • highest keeps the largest salary seen so far.

The answer is (total − lowest − highest) / (n − 2), divided as decimals. It is exact because the salaries are all different: exactly one salary is the lowest and exactly one is the highest, so subtracting each once removes exactly those two employees.

The same salaries in the order given, with 1000 marked lowest and 7000 marked highest: 21000 − 1000 − 7000 = 13000, divided by the 3 salaries left. Whole-number division would give 4333; decimal division gives 4333.33333.

Start lowest and highest at the first salary. Starting lowest at 0 would leave it at 0 for ever, since every salary is at least 1000, and the answer would be too large.

In Python, the built-ins do the same job. sum(salary) - min(salary) - max(salary), divided by len(salary) - 2, reads the array three times, but each read runs as compiled code. Measured, it is the fastest of all here: 1.6 microseconds at n = 100, and 0.015 s for a million salaries. The loop below is kept so that the code reads the same in all three languages.

Step-by-Step Explanation

We trace Example 3 again, now without sorting. The salary being read is blue, the lowest salary so far is green, and the highest so far is orange.

Step 1: total = 0; lowest and highest start at the first salary, 6000.

Step 2: Read 6000: total = 6000.

Step 3: Read 1000: total = 7000. New lowest = 1000.

Step 4: Read 7000: total = 14000. New highest = 7000.

Step 5: Read 2000: total = 16000.

Step 6: Read 5000: total = 21000.

Step 7: Return (21000 − 1000 − 7000) / 3 = 4333.33333.

One Pass: the Total, the Lowest and the Highest — Example 3 in the order given. One pass keeps the running total, the lowest salary so far (green) and the highest so far (orange).

Algorithm

  1. Set total = 0, and lowest and highest both to salary[0].
  2. For each salary s: add s to total, set lowest = min(lowest, s) and highest = max(highest, s).
  3. Return (total − lowest − highest) / (n − 2), dividing as decimals.

Can the total overflow? Not here: it is at most 100 × 10^6 = 10^8, well inside a 32-bit integer (about 2.1 × 10^9). The C++ and Java code still keeps it in a 64-bit long long or long, the habit that stays safe if the limits grow.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    double average(vector<int>& salary) {
        long long total = 0;
        int lowest = salary[0], highest = salary[0];
        for (int s : salary) {
            total += s;
            lowest = min(lowest, s);
            highest = max(highest, s);
        }
        return (double)(total - lowest - highest) / (salary.size() - 2);  // the cast makes this a decimal division
    }
};
class Solution:
    def average(self, salary: list[int]) -> float:
        total, lowest, highest = 0, salary[0], salary[0]
        for s in salary:
            total += s
            lowest = min(lowest, s)
            highest = max(highest, s)
        return (total - lowest - highest) / (len(salary) - 2)
class Solution {
    public double average(int[] salary) {
        long total = 0;
        int lowest = salary[0], highest = salary[0];
        for (int s : salary) {
            total += s;
            lowest = Math.min(lowest, s);
            highest = Math.max(highest, s);
        }
        return (double) (total - lowest - highest) / (salary.length - 2);  // the cast makes this a decimal division
    }
}

Complexity Analysis

Time Complexity: O(n). One pass over the array. Measured in Python, 3.6 microseconds at n = 100 and 0.040 s for a million salaries.

Space Complexity: O(1). Three numbers.

No method can read less. A salary that is never read could be the lowest, the highest, or simply change the total, so every one of the n salaries has to be read, and O(n) is the least any method can do.