Average Salary Excluding the Minimum and Maximum Salary
EasyPrompt
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. Answers within 10-5 of the actual answer will be accepted.
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 = 2500Example 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
Constraints:
3 <= salary.length <= 1001000 <= salary[i] <= 106- All the integers of
salaryare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves sorting the salary array first. After sorting, the minimum salary will be the first element and the maximum salary will be the last. We can then iterate through the rest of the elements, calculate their sum, and divide by the count to find the average.
Algorithm
- Sort the input
salaryarray in ascending order. - Initialize a variable
sumto 0.0. - Loop from the second element (
i = 1) to the second-to-last element (i < salary.length - 1). - In each iteration, add
salary[i]tosum. - After the loop, calculate the average by dividing
sumby(salary.length - 2). - Return the average.
Walkthrough
The core idea is to leverage sorting to easily identify the minimum and maximum salaries. Once the array is sorted in ascending order, the smallest salary is at index 0 and the largest is at index n-1, where n is the number of employees. We can then calculate the sum of salaries from index 1 to n-2. The number of salaries included in this sum is (n-2) - 1 + 1 = n-2. Finally, the average is computed by dividing this sum by n-2.
Algorithm:
- Sort the input
salaryarray. - Initialize a variable
sumto 0.0. - Loop from the second element (
i = 1) to the second-to-last element (i < salary.length - 1). - In each iteration, add
salary[i]tosum. - After the loop, calculate the average by dividing
sumby(salary.length - 2). - Return the average.
import java.util.Arrays; class Solution { public double average(int[] salary) { Arrays.sort(salary); double sum = 0; for (int i = 1; i < salary.length - 1; i++) { sum += salary[i]; } return sum / (salary.length - 2); }}Complexity
Time
O(N log N), where N is the number of salaries. The dominant operation is sorting the array, which typically takes O(N log N) time. The subsequent summation is O(N).
Space
O(log N) or O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Clearly separates the logic of finding min/max from calculating the sum.
Cons
Less efficient than linear time approaches due to the sorting step, which takes O(N log N) time.
Modifies the input array, which might not be desirable in some contexts. A copy would be needed to avoid this, increasing space complexity.
This approach avoids sorting by making two passes over the array. The first pass finds the minimum and maximum salaries. The second pass calculates the sum of all salaries excluding the minimum and maximum found in the first pass.
Algorithm
- Initialize
minSalarytoInteger.MAX_VALUEandmaxSalarytoInteger.MIN_VALUE. - Iterate through the
salaryarray to find the actual minimum and maximum salaries. - Initialize
sumto 0.0. - Iterate through the
salaryarray again. - For each
sinsalary, ifsis notminSalaryand notmaxSalary, addstosum. - Return
sum / (salary.length - 2).
Walkthrough
Instead of sorting, we can find the minimum and maximum salaries by iterating through the array once. We keep track of the minimum and maximum values seen so far. After the first pass, we have the minSalary and maxSalary. Then, we perform a second pass. In this pass, we sum up all the elements that are not equal to minSalary or maxSalary. The average is then this sum divided by n-2. Since all salaries are unique as per the problem constraints, we don't need to worry about multiple occurrences of the min or max value.
Algorithm:
- Initialize
minSalarytoInteger.MAX_VALUEandmaxSalarytoInteger.MIN_VALUE. - Iterate through the
salaryarray to find the actual minimum and maximum salaries. - Initialize
sumto 0.0. - Iterate through the
salaryarray again. - For each
sinsalary, ifsis notminSalaryand notmaxSalary, addstosum. - Return
sum / (salary.length - 2).
class Solution { public double average(int[] salary) { int minSalary = Integer.MAX_VALUE; int maxSalary = Integer.MIN_VALUE; for (int s : salary) { minSalary = Math.min(minSalary, s); maxSalary = Math.max(maxSalary, s); } double sum = 0; for (int s : salary) { if (s != minSalary && s != maxSalary) { sum += s; } } return sum / (salary.length - 2); }}Complexity
Time
O(N), where N is the number of salaries. We iterate through the array twice, which results in O(N) + O(N) = O(N).
Space
O(1). We only use a few extra variables to store the min, max, and sum, regardless of the input size.
Trade-offs
Pros
More efficient than the sorting approach with a linear time complexity.
Does not modify the input array.
Uses constant extra space.
Cons
Requires two passes over the data, which is slightly less optimal than a single-pass solution.
This is the most efficient approach. We can find the minimum salary, maximum salary, and the total sum of all salaries in a single pass through the array. The average is then calculated from these three values.
Algorithm
- Initialize
minSalarytoInteger.MAX_VALUE,maxSalarytoInteger.MIN_VALUE, andsumto 0.0. - Iterate through each salary
sin thesalaryarray. - In each iteration:
- Add
stosum. - Update
minSalary = Math.min(minSalary, s). - Update
maxSalary = Math.max(maxSalary, s).
- Add
- After the loop, calculate the final sum by subtracting
minSalaryandmaxSalaryfrom the totalsum. - Divide this final sum by
(salary.length - 2)to get the average. - Return the result.
Walkthrough
We can optimize the two-pass approach by combining all operations into a single loop. While iterating through the array, we can simultaneously update the minimum salary, the maximum salary, and the running total sum of all salaries. After the loop completes, we will have the total sum of all elements, the absolute minimum element, and the absolute maximum element. The sum of the elements excluding the min and max is simply totalSum - minSalary - maxSalary. The number of elements for the average is n-2. The final result is (totalSum - minSalary - maxSalary) / (n - 2).
Algorithm:
- Initialize
minSalarytoInteger.MAX_VALUE,maxSalarytoInteger.MIN_VALUE, andsumto 0.0. - Iterate through each salary
sin thesalaryarray. - In each iteration:
- Add
stosum. - Update
minSalary = Math.min(minSalary, s). - Update
maxSalary = Math.max(maxSalary, s).
- Add
- After the loop, calculate the final sum by subtracting
minSalaryandmaxSalaryfrom the totalsum. - Divide this final sum by
(salary.length - 2)to get the average. - Return the result.
class Solution { public double average(int[] salary) { int minSalary = Integer.MAX_VALUE; int maxSalary = Integer.MIN_VALUE; double sum = 0; for (int s : salary) { sum += s; minSalary = Math.min(minSalary, s); maxSalary = Math.max(maxSalary, s); } return (sum - minSalary - maxSalary) / (salary.length - 2); }}Complexity
Time
O(N), where N is the number of salaries. We iterate through the array only once, making it the most time-efficient solution.
Space
O(1). We use a constant amount of extra space for variables to store the min, max, and sum.
Trade-offs
Pros
Most efficient in terms of both time and space.
Simple and concise implementation.
Processes the data in a single pass, which can be more cache-friendly than multiple passes.
Cons
There are no significant cons for this approach as it is optimal for the given problem.
Solutions
Solution
class Solution {public double average(int[] salary) { int s = 0; int mi = 10000000, mx = 0; for (int v : salary) { mi = Math.min(mi, v); mx = Math.max(mx, v); s += v; } s -= (mi + mx); return s * 1.0 / (salary.length - 2); }}class Solution {public: double average(vector<int> &salary) { int s = 0; int mi = 1e7, mx = 0; for (int v : salary) { s += v; mi = min(mi, v); mx = max(mx, v); } s -= (mi + mx); return (double)s / (salary.size() - 2); }};class Solution: def average(self, salary: List[int]) -> float: s = sum(salary) - min(salary) - max(salary) return s / (len(salary) - 2)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.