Difficulty: Easy | Acceptance: 63.60% | Paid: No Topics: Array, Sorting
You are given an array of unique integers salary where salary[i] is the salary of the ith employee.
Return the average salary of employees excluding the minimum and maximum salary. The answer within 10⁻⁵ of the actual answer will be accepted.
- Examples
- Constraints
- Sorting Approach
- Linear Scan Approach
- Built-in Functions Approach
Examples
Example 1
Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary is 1000, maximum salary is 4000.
Average salary excluding min and max is (3000+2000)/2 = 2500
Example 2
Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary is 1000, maximum salary is 3000.
Average salary excluding min and max is 2000/1 = 2000
Constraints
- 3 <= salary.length <= 100
- 1000 <= salary[i] <= 10^6
- All the integers of salary are unique.
Sorting Approach
Intuition Sort the array to easily identify and exclude the minimum (first element) and maximum (last element) values.
Steps
- Sort the salary array in ascending order
- Sum all elements except the first (minimum) and last (maximum)
- Divide the sum by (n-2) to get the average
python
class Solution:
def average(self, salary: list[int]) -> float:
salary.sort()
return sum(salary[1:-1]) / (len(salary) - 2)
Complexity
- Time: O(n log n) for sorting
- Space: O(1) or O(n) depending on sorting implementation
- Notes: Simple but not optimal due to sorting overhead
Linear Scan Approach
Intuition Find minimum and maximum values in a single pass, then calculate the average excluding these two values.
Steps
- Initialize min and max variables
- Calculate total sum of all salaries
- Subtract min and max from the total sum
- Divide by (n-2) to get the average
python
class Solution:
def average(self, salary: list[int]) -> float:
min_sal = float('inf')
max_sal = float('-inf')
total = 0
for s in salary:
min_sal = min(min_sal, s)
max_sal = max(max_sal, s)
total += s
return (total - min_sal - max_sal) / (len(salary) - 2)
Complexity
- Time: O(n) - single pass through the array
- Space: O(1) - only using constant extra space
- Notes: Optimal solution with linear time complexity
Built-in Functions Approach
Intuition Use language built-in functions to find min, max, and sum directly.
Steps
- Use built-in min function to find minimum salary
- Use built-in max function to find maximum salary
- Use built-in sum function to get total
- Calculate average excluding min and max
python
class Solution:
def average(self, salary: list[int]) -> float:
return (sum(salary) - min(salary) - max(salary)) / (len(salary) - 2)
Complexity
- Time: O(n) - built-in functions iterate through the array
- Space: O(1) - constant extra space
- Notes: Clean and readable code using language features