#1491

Easy

LeetCode Problem Workspace

Average Salary Excluding the Minimum and Maximum Salary

Calculate the average salary of employees, excluding the highest and lowest salaries, from an array of unique salaries.

Problem Statement

You are given an array of unique integers, where each integer represents the salary of an employee. The task is to return the average salary, excluding the minimum and maximum salary from the array.

The problem requires you to find the average of the salaries after removing the smallest and largest salary values. You can assume that the array will always have at least three salaries.

Examples

Example 1

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

Output: 2500.00000

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

Minimum salary and maximum salary are 1000 and 3000 respectively. Average salary excluding minimum and maximum salary is (2000) / 1 = 2000

Constraints

3 <= salary.length <= 100
1000 <= salary[i] <= 106
All the integers of salary are unique.

Solution Approach

Sorting and Average Calculation

First, sort the salary array to easily access the minimum and maximum salaries. Then, remove these two salaries and compute the average of the remaining salaries.

Sum and Subtraction Approach

Instead of sorting, calculate the total sum of the salaries and subtract the minimum and maximum values. Finally, divide the resulting sum by the number of employees minus two to get the average.

Optimized Approach

Iterate through the salary array once to find the minimum and maximum values. Subtract them from the total sum and divide by the appropriate count to find the average.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. Sorting takes O(n log n), while the sum-based approach can be done in O(n). Space complexity is O(1) if using the sum-based method, and O(n) for sorting.

What Interviewers Usually Probe

Look for the candidate's understanding of array manipulation and their ability to optimize solutions.
Evaluate if the candidate can explain the trade-off between sorting and using sum subtraction.
Assess if the candidate can handle edge cases like arrays with the minimum length of three.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude both the minimum and maximum salaries before calculating the average.
Relying on sorting when the sum-based approach can offer better performance for larger arrays.
Not handling edge cases, such as arrays with exactly three elements or large salary ranges.

Follow-up variants

Modify the problem to include arrays with non-unique salaries and adjust the approach accordingly.
Ask the candidate to optimize for time complexity by avoiding sorting.
Introduce a scenario where the average needs to be calculated after excluding a different number of salary values.

FAQ

What is the time complexity of the sorting approach for this problem?

The sorting approach has a time complexity of O(n log n) due to the sorting step.

How can I optimize the solution to avoid sorting?

You can optimize the solution by calculating the sum of the array, subtracting the minimum and maximum salaries, and then dividing by n-2.

What if the salary array has more than three elements?

The approach remains the same, regardless of the number of elements in the array, as long as there are at least three elements.

What should I do if the problem includes duplicate salaries?

You would need to modify the approach to handle duplicates, either by removing duplicates or adjusting how the minimum and maximum are determined.

How can I handle very large salary values efficiently?

Ensure the algorithm handles large numbers by focusing on O(n) solutions, such as sum-based calculations, to avoid issues with sorting overhead.

terminal

Solution

Solution 1: Simulation

Simulate according to the problem's requirements.

1

2

3

4

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

Continue Practicing

#1498 number of subsequences that satisfy the given sum condition #1481 least number of unique integers after k removals #1502 can make arithmetic progression from sequence