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 = 2500
Example 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] <= 106salary are unique.Problem Overview: You receive an array of unique salaries. The task is to compute the average salary after removing the smallest and largest values. Only the remaining elements contribute to the final average.
Approach 1: Sorting and Slicing (Time: O(n log n), Space: O(1) or O(n) depending on language)
Sort the salary array using a standard sorting algorithm. After sorting, the smallest value appears at index 0 and the largest at index n-1. Ignore those two elements and compute the average of the remaining slice. Most languages allow easy slicing such as salary[1:-1]. This approach is simple and readable, but sorting introduces an unnecessary O(n log n) cost when the order of elements is irrelevant.
Approach 2: Single Traversal (Time: O(n), Space: O(1))
Iterate through the array once while tracking three values: the total sum, the minimum salary, and the maximum salary. During each step, update the running sum and compare the current value against the tracked min and max. After the loop finishes, subtract the min and max from the sum and divide by n - 2. This avoids sorting entirely and processes the array in linear time. The approach relies on simple operations over an array, making it both optimal and memory efficient.
The key insight is that you don't need the salaries in order. You only need the smallest and largest values, which can be tracked during iteration. This transforms the problem from a sorting task into a simple aggregation pass.
Recommended for interviews: The single traversal approach. Sorting demonstrates correctness but wastes time complexity. Tracking sum, min, and max in one pass shows stronger understanding of array processing and algorithmic optimization.
One straightforward way to solve this problem is to sort the array and then ignore the first and last elements (which will be the minimum and maximum once sorted). After this, calculate the average of the remaining elements.
This approach leverages the fact that sorting will automatically place the minimum value at the beginning and the maximum value at the end of the array, allowing us to easily exclude them by slicing the array.
The implementation sorts the salary list. Then, it calculates the sum of the array, excluding the first and last elements which are the minimum and maximum values after sorting. The average is then computed by dividing this sum by the number of remaining elements, which is the total length minus 2.
Python
JavaScript
Java
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) in the worst case due to the sorting algorithm.
Instead of sorting, we can solve the problem using a single pass through the array. We find the minimum and maximum while calculating the total sum of elements. After determining the sum, minimum, and maximum, the average can be easily calculated by excluding the minimum and maximum from the sum.
C++ uses a loop to compute the total sum of salaries while simultaneously finding the minimum and maximum values. This avoids sorting and hence can be more efficient. After obtaining these values, the minimum and maximum are subtracted from the total sum to compute the average of the remaining elements.
Time Complexity: O(n), as it requires a single pass to determine the sum, minimum, and maximum.
Space Complexity: O(1), since no additional data structures are used apart from a few variables.
Simulate according to the problem's requirements.
Traverse the array, find the maximum and minimum values, and accumulate the sum. Then calculate the average value after removing the maximum and minimum values.
The time complexity is O(n), where n is the length of the array salary. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sorting and Slicing | Time Complexity: O(n log n) due to the sorting step. |
| Single Traversal | Time Complexity: O(n), as it requires a single pass to determine the sum, minimum, and maximum. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Slicing | O(n log n) | O(1) or O(n) | Quick implementation when sorting utilities are convenient or readability is preferred |
| Single Traversal | O(n) | O(1) | Optimal solution for interviews and large inputs since it avoids sorting |
LeetCode#1491 Average Salary Excluding the Minimum and Maximum Salary - Python • CodeJulian • 1,372 views views
Watch 9 more video solutions →Practice Average Salary Excluding the Minimum and Maximum Salary with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor