LeetCode 1491 - Average Salary Excluding the Minimum and Maximum Salary

LeetCode Problem 1491

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem gives us an array called salary, where each element represents the salary of an employee. Every salary value is unique, meaning no two employees have the same salary. Our task is to compute the average salary after excluding exactly one minimum salary and one maximum salary from the array.

In other words, we must:

1. Find the smallest salary.
2. Find the largest salary.
3. Ignore both of them.
4. Compute the average of all remaining salaries.

The return value must be a floating point number. The problem statement also specifies that answers within 10^-5 of the correct value are accepted, so standard floating point arithmetic is sufficient.

The input size is small:

• 3 <= salary.length <= 100
• 1000 <= salary[i] <= 10^6

These constraints tell us several important things:

• The array always contains at least three elements, so after removing the minimum and maximum salaries, there will always be at least one value left to average.
• Since all salaries are unique, there is exactly one minimum and exactly one maximum.
• The input size is tiny, so even less efficient approaches would still pass comfortably.

A naive implementation could accidentally include the minimum or maximum in the sum, or incorrectly divide by the original array length instead of the reduced length. Another common mistake is performing integer division instead of floating point division, especially in languages like Go.

The problem guarantees that:

• There is always a valid answer.
• The minimum and maximum are distinct because all salaries are unique.
• We never need to handle an empty remaining array.

Approaches

Brute Force Approach

A straightforward solution is to sort the array first. After sorting:

• The first element is the minimum salary.
• The last element is the maximum salary.
• Every element in between should be included in the average.

We can then iterate through the middle portion of the sorted array, compute the sum, and divide by the number of remaining elements.

This approach is correct because sorting places all salaries in increasing order, making it trivial to identify the smallest and largest values.

However, sorting requires O(n log n) time, which is more work than necessary. We do not actually care about the relative ordering of all salaries, we only need the minimum, maximum, and total sum.

Optimal Approach

The key observation is that we can compute everything we need in a single pass through the array.

During one traversal:

• Track the minimum salary seen so far.
• Track the maximum salary seen so far.
• Maintain the running total sum.

At the end:

• Subtract the minimum and maximum from the total sum.
• Divide by n - 2, because two salaries were excluded.

This works because the average only depends on:

$$\text{average} = \frac{\text{total sum} - \text{min} - \text{max}}{n - 2}$$

We never need to rearrange the array, so sorting is unnecessary.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1) or O(n)	Sorts the array, then averages the middle elements
Optimal	O(n)	O(1)	Single pass tracking sum, minimum, and maximum

Algorithm Walkthrough

Optimal Algorithm

1. Initialize three variables:

• total_sum to store the sum of all salaries.
• minimum_salary to track the smallest value.
• maximum_salary to track the largest value.

2. Traverse the array once.

• Add each salary to total_sum.
• Update minimum_salary if the current salary is smaller.
• Update maximum_salary if the current salary is larger.

3. After the traversal completes:

• Subtract minimum_salary and maximum_salary from total_sum.
• This leaves only the salaries that should contribute to the average.

4. Compute the number of remaining salaries.

• Since exactly two salaries are excluded, the count is len(salary) - 2.

5. Divide the adjusted sum by the adjusted count.

• Return the result as a floating point number.

Why it works

The algorithm works because every salary belongs to exactly one of three categories:

• The minimum salary
• The maximum salary
• A salary that should contribute to the average

By computing the total sum of all salaries and then removing the minimum and maximum values, we are left with exactly the salaries we want to average. Since we also divide by the correct number of remaining elements, the result is mathematically correct.

Python Solution

from typing import List

class Solution:
    def average(self, salary: List[int]) -> float:
        total_sum = 0
        minimum_salary = float("inf")
        maximum_salary = float("-inf")

        for current_salary in salary:
            total_sum += current_salary
            minimum_salary = min(minimum_salary, current_salary)
            maximum_salary = max(maximum_salary, current_salary)

        adjusted_sum = total_sum - minimum_salary - maximum_salary
        remaining_count = len(salary) - 2

        return adjusted_sum / remaining_count

The implementation follows the optimal single pass approach directly.

The variable total_sum accumulates the sum of all salaries. At the same time, minimum_salary and maximum_salary keep track of the smallest and largest values encountered during traversal.

Using float("inf") and float("-inf") ensures that the first salary processed correctly initializes both minimum and maximum values.

After the loop finishes, the code removes the minimum and maximum salaries from the total sum. The remaining salaries are exactly the ones that should contribute to the average.

Finally, the adjusted sum is divided by len(salary) - 2, which represents the number of salaries left after excluding two values.

Go Solution

func average(salary []int) float64 {
    totalSum := 0
    minimumSalary := salary[0]
    maximumSalary := salary[0]

    for _, currentSalary := range salary {
        totalSum += currentSalary

        if currentSalary < minimumSalary {
            minimumSalary = currentSalary
        }

        if currentSalary > maximumSalary {
            maximumSalary = currentSalary
        }
    }

    adjustedSum := totalSum - minimumSalary - maximumSalary
    remainingCount := len(salary) - 2

    return float64(adjustedSum) / float64(remainingCount)
}

The Go implementation is very similar to the Python version, but there are a few language specific considerations.

Go performs integer division when both operands are integers, so both adjustedSum and remainingCount must be converted to float64 before division.

Instead of using infinity values, the Go solution initializes both minimumSalary and maximumSalary with the first element of the slice. This is a common Go pattern when tracking minimum and maximum values.

Since the constraints guarantee at least three salaries, accessing salary[0] is always safe.

Worked Examples

Example 1

Input:

salary = [4000, 3000, 1000, 2000]

Step by Step Trace

Iteration	Current Salary	Total Sum	Minimum	Maximum
Start	-	0	inf	-inf
1	4000	4000	4000	4000
2	3000	7000	3000	4000
3	1000	8000	1000	4000
4	2000	10000	1000	4000

After traversal:

adjusted_sum = 10000 - 1000 - 4000 = 5000
remaining_count = 4 - 2 = 2
average = 5000 / 2 = 2500.0

Final answer:

2500.00000

Example 2

Input:

salary = [1000, 2000, 3000]

Step by Step Trace

Iteration	Current Salary	Total Sum	Minimum	Maximum
Start	-	0	inf	-inf
1	1000	1000	1000	1000
2	2000	3000	1000	2000
3	3000	6000	1000	3000

After traversal:

adjusted_sum = 6000 - 1000 - 3000 = 2000
remaining_count = 3 - 2 = 1
average = 2000 / 1 = 2000.0

Final answer:

2000.00000

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is traversed exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the input array. Each salary is processed once, so the running time grows linearly with the number of employees.

The memory usage remains constant because the algorithm only stores a few scalar variables, regardless of how large the input becomes.

Test Cases

from typing import List

class Solution:
    def average(self, salary: List[int]) -> float:
        total_sum = 0
        minimum_salary = float("inf")
        maximum_salary = float("-inf")

        for current_salary in salary:
            total_sum += current_salary
            minimum_salary = min(minimum_salary, current_salary)
            maximum_salary = max(maximum_salary, current_salary)

        return (
            total_sum - minimum_salary - maximum_salary
        ) / (len(salary) - 2)

solution = Solution()

assert solution.average([4000, 3000, 1000, 2000]) == 2500.0  # provided example
assert solution.average([1000, 2000, 3000]) == 2000.0  # smallest valid array size
assert solution.average([6000, 5000, 4000, 3000, 2000, 1000]) == 3500.0  # descending order
assert solution.average([1000, 2000, 3000, 4000, 5000]) == 3000.0  # ascending order
assert solution.average([1000000, 1000, 500000]) == 500000.0  # large salary range
assert solution.average([8000, 9000, 1000, 3000, 6000]) == 5666.666666666667  # fractional average
assert solution.average([7000, 3000, 5000]) == 5000.0  # only one value remains after exclusion

Test	Why
[4000, 3000, 1000, 2000]	Validates the primary example
[1000, 2000, 3000]	Tests minimum allowed array size
Descending order input	Ensures ordering does not matter
Ascending order input	Verifies correct min/max exclusion
Large salary values	Confirms handling of large integers
Fractional average case	Ensures floating point division is correct
Three element array	Verifies handling when only one value remains

Edge Cases

One important edge case is the minimum allowed array size of three elements. In this situation, removing the minimum and maximum salaries leaves exactly one salary remaining. A buggy implementation might incorrectly divide by zero or mishandle the reduced array size. This implementation correctly divides by len(salary) - 2, which becomes 1.

Another important edge case is when the salaries are already sorted in ascending or descending order. Some implementations accidentally assume random ordering or rely too heavily on positional logic. Since this solution explicitly tracks minimum and maximum values during traversal, the original ordering has no effect on correctness.

A third important edge case involves very large salary values near the upper constraint limit of 10^6. If a language used small integer types, overflow could become a concern. Both Python integers and Go's standard int type comfortably handle the maximum possible sum under these constraints, so the implementation remains safe and correct.

A final subtle edge case is fractional averages. Not every adjusted sum divides evenly by the remaining count. An implementation using integer division would truncate the decimal portion and produce incorrect results. Both solutions explicitly use floating point division to preserve precision.