Average Salary Excluding the Minimum and Maximum Salary solution and explanation
9 more videos on this problem
Leetcode | 1491. Average Salary Excluding the Minimum and Maximum Salary | Easy | Java SolutionDeveloper Docs · 5:41 · 1K views
Average Salary Excluding the Minimum and Maximum Salary | Leetcode 1491 | Top interview questionSuper Lazy Coder · 7:01 · 806 views
Solution of Leetcode 1491. Average Salary Excluding the Minimum and Maximum Salary(nlogn and n)Faceless Engineer · 11:48 · 790 views
1491. Average Salary Excluding the Minimum and Maximum Salary (Leetcode Easy)Programming Live with Larry · 2:04 · 661 views
1491. Average Salary Excluding the Minimum and Maximum Salary - Daily Leetcode (Day 40)yeetcode · 3:30 · 504 views
Average Salary Excluding the Minimum and Maximum Salary - Leetcode 1491 - PythonTechError · 4:29 · 404 views
How to Solve "1491 Average Salary Excluding the Minimum and Maximum Salary" on LeetCode?Becoming A Better Dev (with David) · 4:45 · 333 views
1491 Average Salary Excluding the Minimum and Maximum Salary | Leetcode with Python #youtubeArsalan Ahmed · 4:03 · 252 views
LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary Solution Explained - JavaAlgorithms and Data Structures Course · 9:04 · 227 views
Daily Leetcode #1126: May 01, 2023 - 1491. Average Salary Excluding the Minimum and Maximum SalaryProgramming Live with Larry · 2:42 · 220 views
The problem
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] <= 106- All the integers of
salaryare unique.
Approach overview
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.
Approach 1: Sorting and Slicing
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.
def average_excluding_min_max(salary):
salary.sort()
return sum(salary[1:-1]) / (len(salary) - 2)import java.util.Arrays;
public class AverageSalary {
public static double average(int[] salary) {
Arrays.sort(salary);
int sum = 0;
for (int i = 1; i < salary.length - 1; i++) {
sum += salary[i];
}
return sum / (double) (salary.length - 2);
}
}function averageExcludingMinMax(salary) {
salary.sort((a, b) => a - b);
const sum = salary.slice(1, -1).reduce((acc, val) => acc + val, 0);
return sum / (salary.length - 2);
}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.
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) in the worst case due to the sorting algorithm.
Approach 2: Single Traversal
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.
#include <vector>
#include <algorithm>
using namespace std;
double average(vector<int>& salary) {
int minSalary = INT_MAX, maxSalary = INT_MIN;
int total = 0;
for(int s : salary) {
minSalary = min(minSalary, s);
maxSalary = max(maxSalary, s);
total += s;
}
return (total - minSalary - maxSalary) / ((double)salary.size() - 2);
}using System;
public class AverageSalary {
public static double Average(int[] salary) {
int minSalary = int.MaxValue, maxSalary = int.MinValue;
int total = 0;
foreach (int s in salary) {
minSalary = Math.Min(minSalary, s);
maxSalary = Math.Max(maxSalary, s);
total += s;
}
return (double)(total - minSalary - maxSalary) / (salary.Length - 2);
}
}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.
Approach 3: Simulation
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).
function average(salary: number[]): number {
let max = -Infinity;
let min = Infinity;
let sum = 0;
for (const v of salary) {
sum += v;
max = Math.max(max, v);
min = Math.min(min, v);
}
return (sum - max - min) / (salary.length - 2);
}#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
double average(int* salary, int salarySize) {
int ma = INT_MIN;
int mi = INT_MAX;
int sum = 0;
for (int i = 0; i < salarySize; i++) {
sum += salary[i];
ma = max(ma, salary[i]);
mi = min(mi, salary[i]);
}
return (sum - mi - ma) * 1.0 / (salarySize - 2);
}func average(salary []int) float64 {
s := 0
mi, mx := 10000000, 0
for _, v := range salary {
s += v
mi = min(mi, v)
mx = max(mx, v)
}
s -= (mi + mx)
return float64(s) / float64(len(salary)-2)
}impl Solution {
pub fn average(salary: Vec<i32>) -> f64 {
let n = salary.len() as i32;
let mut min = i32::MAX;
let mut max = i32::MIN;
let mut sum = 0;
for &num in salary.iter() {
min = min.min(num);
max = max.max(num);
sum += num;
}
f64::from(sum - min - max) / f64::from(n - 2)
}
}class Solution {
/**
* @param Integer[] $salary
* @return Float
*/
function average($salary) {
$max = $sum = 0;
$min = 10 ** 6;
for ($i = 0; $i < count($salary); $i++) {
$min = min($min, $salary[$i]);
$max = max($max, $salary[$i]);
$sum += $salary[$i];
}
return ($sum - $max - $min) / (count($salary) - 2);
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Average Salary Excluding the Minimum and Maximum Salary easy or hard?
The problem is classified as Easy on LeetCode. It focuses on basic array processing and simple arithmetic, but interviewers often expect the optimized O(n) traversal instead of the sorting-based approach.
Average Salary Excluding the Minimum and Maximum Salary Python/Java solution
In Python or Java, the solution typically tracks sum, min, and max in a loop. After processing the array, compute (sum - min - max) / (n - 2). Python may also use slicing after sorting, while Java implementations usually prefer the single-pass O(n) method.
How to solve Average Salary Excluding the Minimum and Maximum Salary in O(n)?
Iterate through the salary array once while maintaining three variables: total sum, minimum salary, and maximum salary. After the loop, subtract the min and max from the total sum and divide by n-2 to compute the average of the remaining elements.
What is the best approach for Average Salary Excluding the Minimum and Maximum Salary?
The best approach is a single traversal of the array. Track the running sum, minimum value, and maximum value during one pass, then subtract the min and max from the total and divide by n-2. This runs in O(n) time with O(1) space and avoids the overhead of sorting.
Is Average Salary Excluding the Minimum and Maximum Salary asked at Google/Amazon/Meta?
This problem reflects a common interview pattern focused on array traversal and aggregation. Similar problems appear in interviews at companies like Amazon and Google where candidates must compute statistics from arrays using optimal time complexity.
What data structure is used in Average Salary Excluding the Minimum and Maximum Salary?
The problem primarily uses an array as the input data structure. The optimal solution performs a linear scan over the array while tracking numeric values such as the sum, minimum, and maximum.
What is the time complexity of Average Salary Excluding the Minimum and Maximum Salary?
The optimal solution runs in O(n) time because the array is scanned once while tracking the sum, minimum, and maximum values. A simpler sorting-based approach takes O(n log n) time due to the sorting step.