Average Salary Excluding the Minimum and Maximum Salary

EASY

Description

You are given an array of unique integers salary where salary[i] is the salary of the i^th 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] <= 10⁶
All the integers of salary are unique.

Approaches

Checkout 3 different approaches to solve Average Salary Excluding the Minimum and Maximum Salary. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Average Salary Excluding the Minimum and Maximum Salary. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Average Salary Excluding the Minimum and Maximum Salary

Algorithms:

Sorting

Data Structures:

Array

Companies:

Netsuite |