1491. Average Salary Excluding the Minimum and Maximum Salary
Problem Description
The given LeetCode problem presents you with an array named salary which contains integers that represent the salaries of employees. Each integer in the array is unique and corresponds to the salary of an individual employee. Your task is to calculate the average salary after excluding the maximum and minimum salary from the calculation. The result should be close to the actual average, within a tolerance of 10^-5. Basically, you're filtering out the outliers (the highest and the lowest salaries) to find the average salary that represents the majority of employees more accurately.
Intuition
To solve this problem, the intuitive approach is to first eliminate the outliers since we want an average that doesn't include the extremes (minimum and maximum values). We do this by:
- Calculating the sum of all elements in the
salaryarray, which would initially include the minimum and maximum salaries. - Then, subtract the minimum salary and the maximum salary from this sum to exclude their influence on the overall average.
- Finally, we divide the adjusted sum by the total count of salaries excluding the two removed salaries (the minimum and maximum ones).
The length of the adjusted salary array is len(salary) - 2 because we have removed two elements (the smallest and the largest).
By performing this simple arithmetic operation, we reach the efficient solution to calculate the required average. The provided code neatly encapsulates this approach and directly uses Python's built-in functions sum(), min(), and max() to compute it. The results are then returned after performing the division, giving us the average salary excluding the minimum and maximum salaries.
Learn more about Sorting patterns.
What are the most two important steps in writing a depth first search function? (Select 2)
Solution Approach
The Reference Solution Approach leverages built-in functions in Python without the need for any additional algorithms, data structures, or patterns. The approach is very straight-forward and efficient, following a simple set of operations:
-
Calculate Total Salary: This is done by using Python's
sum()function that adds up all elements in thesalaryarray.1total_salary = sum(salary) -
Find Minimum and Maximum Salary: Python provides
min()andmax()functions that are used to find the smallest and largest values in thesalaryarray, respectively.1minimum_salary = min(salary) 2maximum_salary = max(salary) -
Exclude Minimum and Maximum Salaries: To exclude these values from our calculations, we subtract them from the
total_salary.1adjusted_salary = total_salary - minimum_salary - maximum_salary -
Calculate Average Salary: To find the average, we divide the
adjusted_salaryby the number of remaining salaries. Since we excluded the minimum and maximum salaries, we havelen(salary) - 2employees remaining.1average_salary = adjusted_salary / (len(salary) - 2) -
Return the Result: The final step in our solution is to return the calculated average salary.
1return average_salary
The provided code executes these steps sequentially in a single method, compacting the operations into a concise one-liner. This straightforward implementation minimizes complexity and makes the code easy to understand and maintain. It's a typical pattern for solving problems involving arrays and basic statistics in programming, utilizing only the fundamental built-in functions and operations of the Python language.
Which of these pictures shows the visit order of a depth-first search?
Example Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have an array salary that represents the salaries of employees as follows:
1salary = [4000, 3000, 5000, 2000, 6000]
Step 1: Calculate Total Salary
Using the sum() function, we sum up all salaries:
1total_salary = sum(salary) # total_salary = 20000
Step 2: Find Minimum and Maximum Salary
We find the minimum and maximum salaries using min() and max() functions:
1minimum_salary = min(salary) # minimum_salary = 2000
2maximum_salary = max(salary) # maximum_salary = 6000
Step 3: Exclude Minimum and Maximum Salaries
Next, we subtract both these values from the total salary to exclude their effect:
1adjusted_salary = total_salary - minimum_salary - maximum_salary # adjusted_salary = 12000
Step 4: Calculate Average Salary
To calculate the average, we now divide by the number of remaining salaries (which is len(salary) - 2 because we're not counting the minimum and maximum):
1count = len(salary) - 2 # count = 3
2average_salary = adjusted_salary / count # average_salary = 4000
Step 5: Return the Result
Finally, we return the average salary, excluding the highest and lowest salaries:
1return average_salary # returns 4000
This average salary (4000) is the output, and in this example, it is equal to one of the employee's salaries, which is more representative of the majority when the outliers are removed.
Solution Implementation
1from typing import List # Import List from typing to use for type hinting
2
3class Solution:
4 def average(self, salaries: List[int]) -> float:
5 """
6 Calculate the average salary after excluding the minimum and maximum salary.
7
8 :param salaries: List of salaries from which to calculate the average.
9 :return: The average salary as a float.
10 """
11 # Calculate the sum of all salaries and subtract the minimum and maximum salary
12 total_salary_except_min_max = sum(salaries) - min(salaries) - max(salaries)
13
14 # Calculate the average salary by dividing the total_salary_except_min_max by
15 # the number of salaries minus 2 (since we excluded the min and max salaries)
16 average_salary = total_salary_except_min_max / (len(salaries) - 2)
17
18 return average_salary
191class Solution {
2 public double average(int[] salary) {
3 // Initialize sum of salaries to 0
4 int sum = 0;
5 // Initialize minimum salary to the largest possible integer value
6 int minSalary = Integer.MAX_VALUE;
7 // Initialize maximum salary to the smallest possible integer value
8 int maxSalary = Integer.MIN_VALUE;
9
10 // Iterate over all the salaries
11 for (int value : salary) {
12 // Update minimum salary if a smaller salary is found
13 minSalary = Math.min(minSalary, value);
14 // Update maximum salary if a larger salary is found
15 maxSalary = Math.max(maxSalary, value);
16 // Accumulate sum of all salaries
17 sum += value;
18 }
19
20 // Subtract the extreme values (min and max salary) from the total sum
21 sum -= (minSalary + maxSalary);
22
23 // Calculate average: divide the modified sum by the number of elements excluding the two extremes
24 return sum * 1.0 / (salary.length - 2);
25 }
26}
271#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to calculate the average salary excluding the minimum and maximum salary.
7 double average(std::vector<int>& salary) {
8 int sum = 0; // Initialize sum of all salaries to 0
9 int minSalary = INT_MAX; // Initialize minimum salary to the highest possible integer
10 int maxSalary = INT_MIN; // Initialize maximum salary to the lowest possible integer
11
12 // Loop to calculate the total sum and find min and max salary
13 for (int currentValue : salary) {
14 sum += currentValue; // Add the current value to the sum
15 minSalary = std::min(minSalary, currentValue); // Update minSalary if the current value is smaller
16 maxSalary = std::max(maxSalary, currentValue); // Update maxSalary if the current value is larger
17 }
18
19 // Remove the min and max salary from the sum
20 sum -= (minSalary + maxSalary);
21
22 // Calculate the average by dividing the sum by the size of the array minus 2 (since we excluded 2 salaries)
23 return static_cast<double>(sum) / (salary.size() - 2);
24 }
25};
261// Define a function to calculate the average salary excluding the minimum and maximum salary values.
2function average(salary: number[]): number {
3 // Initialize maximum salary seen so far to the lowest possible number.
4 let maxSalary = Number.MIN_VALUE;
5 // Initialize minimum salary seen so far to the highest possible number.
6 let minSalary = Number.MAX_VALUE;
7 // Initialize sum of all salaries to zero.
8 let totalSalary = 0;
9
10 // Iterate through each salary value in the array.
11 for (const value of salary) {
12 // Add current salary to the total sum.
13 totalSalary += value;
14 // Update maximum salary if the current value is greater.
15 maxSalary = Math.max(maxSalary, value);
16 // Update minimum salary if the current value is lower.
17 minSalary = Math.min(minSalary, value);
18 }
19
20 // Subtract the maximum and minimum salary from the total sum
21 // and divide by the length of the array minus 2 (excuding min and max salaries)
22 return (totalSalary - maxSalary - minSalary) / (salary.length - 2);
23}
24How many times is a tree node visited in a depth first search?
Time and Space Complexity
Time Complexity
The given Python code consists of finding the minimum and maximum values, summing the elements of the salary list, subtracting the minimum and maximum values from the sum, and finally computing the average by dividing by the number of elements minus 2. Here's how the time complexity breaks down:
min(salary)andmax(salary)each run inO(n)time wherenis the number of elements in the salary list, as the function needs to check each element to determine the minimum or maximum value.sum(salary)also runs inO(n)time, as it adds each element in the list once.- Subtracting the minimum and maximum from the sum and dividing by
n - 2are constant time operations,O(1).
All of these are sequential operations. Therefore, the overall time complexity is O(n) since we sum the individual complexities: O(n) + O(n) + O(n) + O(1) which simplifies to O(n).
Space Complexity
The space complexity of the code is the amount of memory used above and beyond the input itself. Since the code only uses additional space for a few variables (s which holds the sum after subtracting the minimum and maximum salaries), the space complexity is O(1), or constant space, because the space used does not increase with the size of the input list.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.