1491. Average Salary Excluding the Minimum and Maximum Salary
Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 68.5%
Problem Breakdown
The problem requires calculating the average salary of employees excluding the minimum and maximum salaries from a given array of unique integers representing employee salaries. The input is an array salary where each element is a unique integer within the range [10^3, 10^6]. The output should be the average of the remaining salaries after removing the smallest and largest values.
Inputs:
- An array of integers
salarywith at least 3 elements and at most 100 elements. - Each element in the array is a unique integer within the range
[10^3, 10^6].
Outputs:
- A floating-point number representing the average salary excluding the minimum and maximum salaries.
Implicit Constraints or Tricky Edge Cases:
- The array always has at least three elements, so there will always be at least one salary to consider after removing the min and max.
- All salaries are unique, which simplifies finding the min and max values.
- The result should be accurate within
10^-5of the actual value.
Intuition
A brute-force approach would involve sorting the array, removing the first and last elements (min and max), and then calculating the average. However, this approach has a time complexity of O(n log n) due to the sorting step, which is not optimal given that we only need to find the min and max values.
The key insight is to iterate through the array once to simultaneously find both the minimum and maximum salaries while also calculating the total sum of all salaries. This allows us to compute the average in a single pass with O(n) time complexity.
Approach
- Initialize variables
total_sum,min_salary, andmax_salaryto store the cumulative sum, smallest salary, and largest salary respectively. - Iterate through each salary in the array:
- Add the current salary to
total_sum. - Update
min_salaryif the current salary is smaller than the currentmin_salary. - Update
max_salaryif the current salary is larger than the currentmax_salary.
- Add the current salary to
- Calculate the adjusted total sum by subtracting
min_salaryandmax_salaryfromtotal_sum. - Compute the average by dividing the adjusted total sum by the number of remaining salaries (i.e.,
len(salary) - 2). - Return the computed average.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the salary array. We only make a single pass through the array to find the min, max, and total sum.
- Space Complexity: O(1), as we are using a constant amount of extra space regardless of the input size.
Solution
def average(salary):
# Initialize variables to store total sum, minimum salary, and maximum salary
total_sum = 0
min_salary = float('inf')
max_salary = float('-inf')
# Iterate through each salary in the array
for s in salary:
total_sum += s
if s < min_salary:
min_salary = s
if s > max_salary:
max_salary = s
# Calculate adjusted total sum by excluding min and max salaries
adjusted_total_sum = total_sum - min_salary - max_salary
# Compute the average of remaining salaries
average_salary = adjusted_total_sum / (len(salary) - 2)
return average_salary
# Example usage:
# print(average([4000,3000,1000,2000])) # Output: 2500.00000
Edge Cases Handled
- Minimum and Maximum at Ends: If the minimum salary is the first element and the maximum is the last, or vice versa, the algorithm correctly excludes them.
- All Salaries Equal Except Two: The unique constraint ensures that there are always distinct min and max values to exclude.
- Typical Case with Distinct Values: Any typical input where all salaries are distinct will be handled correctly by finding the correct min and max.