# Average Salary Excluding the Minimum and Maximum Salary
**Difficulty:** EASY
[External](https://leetcode.com/problems/average-salary-excluding-the-minimum-and-maximum-salary)
Canonical: https://scaleengineer.com/dsa/problems/average-salary-excluding-the-minimum-and-maximum-salary
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Netsuite](https://scaleengineer.com/companies/netsuite)
---
## 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 <= 100`
* `1000 <= salary[i] <= 106`
* All the integers of `salary` are **unique**.

# Approaches
## Sorting Approach
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.
**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.
**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.
### Explanation
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 `salary` array.
*   Initialize a variable `sum` to 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]` to `sum`.
*   After the loop, calculate the average by dividing `sum` by `(salary.length - 2)`.
*   Return the average.

```java
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);
    }
}
```
### Algorithm
*   Sort the input `salary` array in ascending order.
*   Initialize a variable `sum` to 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]` to `sum`.
*   After the loop, calculate the average by dividing `sum` by `(salary.length - 2)`.
*   Return the average.

## Two-Pass Linear Scan
This approach avoids sorting by making two passes over the array. The first pass finds the minimum and maximum salaries. The second pass calculates the sum of all salaries excluding the minimum and maximum found in the first pass.
**Time:** O(N), where N is the number of salaries. We iterate through the array twice, which results in O(N) + O(N) = O(N). · **Space:** O(1). We only use a few extra variables to store the min, max, and sum, regardless of the input size.
**Pros:** More efficient than the sorting approach with a linear time complexity.; Does not modify the input array.; Uses constant extra space.
**Cons:** Requires two passes over the data, which is slightly less optimal than a single-pass solution.
### Explanation
Instead of sorting, we can find the minimum and maximum salaries by iterating through the array once. We keep track of the minimum and maximum values seen so far. After the first pass, we have the `minSalary` and `maxSalary`. Then, we perform a second pass. In this pass, we sum up all the elements that are not equal to `minSalary` or `maxSalary`. The average is then this sum divided by `n-2`. Since all salaries are unique as per the problem constraints, we don't need to worry about multiple occurrences of the min or max value.

**Algorithm:**
*   Initialize `minSalary` to `Integer.MAX_VALUE` and `maxSalary` to `Integer.MIN_VALUE`.
*   Iterate through the `salary` array to find the actual minimum and maximum salaries.
*   Initialize `sum` to 0.0.
*   Iterate through the `salary` array again.
*   For each `s` in `salary`, if `s` is not `minSalary` and not `maxSalary`, add `s` to `sum`.
*   Return `sum / (salary.length - 2)`.

```java
class Solution {
    public double average(int[] salary) {
        int minSalary = Integer.MAX_VALUE;
        int maxSalary = Integer.MIN_VALUE;
        for (int s : salary) {
            minSalary = Math.min(minSalary, s);
            maxSalary = Math.max(maxSalary, s);
        }

        double sum = 0;
        for (int s : salary) {
            if (s != minSalary && s != maxSalary) {
                sum += s;
            }
        }
        return sum / (salary.length - 2);
    }
}
```
### Algorithm
*   Initialize `minSalary` to `Integer.MAX_VALUE` and `maxSalary` to `Integer.MIN_VALUE`.
*   Iterate through the `salary` array to find the actual minimum and maximum salaries.
*   Initialize `sum` to 0.0.
*   Iterate through the `salary` array again.
*   For each `s` in `salary`, if `s` is not `minSalary` and not `maxSalary`, add `s` to `sum`.
*   Return `sum / (salary.length - 2)`.

## Single-Pass Linear Scan
This is the most efficient approach. We can find the minimum salary, maximum salary, and the total sum of all salaries in a single pass through the array. The average is then calculated from these three values.
**Time:** O(N), where N is the number of salaries. We iterate through the array only once, making it the most time-efficient solution. · **Space:** O(1). We use a constant amount of extra space for variables to store the min, max, and sum.
**Pros:** Most efficient in terms of both time and space.; Simple and concise implementation.; Processes the data in a single pass, which can be more cache-friendly than multiple passes.
**Cons:** There are no significant cons for this approach as it is optimal for the given problem.
### Explanation
We can optimize the two-pass approach by combining all operations into a single loop. While iterating through the array, we can simultaneously update the minimum salary, the maximum salary, and the running total sum of all salaries. After the loop completes, we will have the total sum of all elements, the absolute minimum element, and the absolute maximum element. The sum of the elements excluding the min and max is simply `totalSum - minSalary - maxSalary`. The number of elements for the average is `n-2`. The final result is `(totalSum - minSalary - maxSalary) / (n - 2)`.

**Algorithm:**
*   Initialize `minSalary` to `Integer.MAX_VALUE`, `maxSalary` to `Integer.MIN_VALUE`, and `sum` to 0.0.
*   Iterate through each salary `s` in the `salary` array.
*   In each iteration:
    *   Add `s` to `sum`.
    *   Update `minSalary = Math.min(minSalary, s)`.
    *   Update `maxSalary = Math.max(maxSalary, s)`.
*   After the loop, calculate the final sum by subtracting `minSalary` and `maxSalary` from the total `sum`.
*   Divide this final sum by `(salary.length - 2)` to get the average.
*   Return the result.

```java
class Solution {
    public double average(int[] salary) {
        int minSalary = Integer.MAX_VALUE;
        int maxSalary = Integer.MIN_VALUE;
        double sum = 0;
        for (int s : salary) {
            sum += s;
            minSalary = Math.min(minSalary, s);
            maxSalary = Math.max(maxSalary, s);
        }
        return (sum - minSalary - maxSalary) / (salary.length - 2);
    }
}
```
### Algorithm
*   Initialize `minSalary` to `Integer.MAX_VALUE`, `maxSalary` to `Integer.MIN_VALUE`, and `sum` to 0.0.
*   Iterate through each salary `s` in the `salary` array.
*   In each iteration:
    *   Add `s` to `sum`.
    *   Update `minSalary = Math.min(minSalary, s)`.
    *   Update `maxSalary = Math.max(maxSalary, s)`.
*   After the loop, calculate the final sum by subtracting `minSalary` and `maxSalary` from the total `sum`.
*   Divide this final sum by `(salary.length - 2)` to get the average.
*   Return the result.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  double average(vector<int> &salary) {
    int s = 0;
    int mi = 1e7, mx = 0;
    for (int v : salary) {
      s += v;
      mi = min(mi, v);
      mx = max(mx, v);
    }
    s -= (mi + mx);
    return (double)s / (salary.size() - 2);
  }
};

```

### Python

```python
class Solution:
    def average(self, salary: List[int]) -> float: s = sum(salary) - min(salary) - max(salary) return s / (len(salary) - 2)

```