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.
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); }}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.