Teaching Kids Programming – Compute Average of an Array Excluding Max and Min

Teaching Kids Programming: Videos on Data Structures and Algorithms

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] <= 10^6
All the integers of salary are unique.

Algorithms to Compute Average of an Array Excluding Max and Min

There are quite a few ways to compute the average for an array of numbers excluding max and min. The average is computed as the sum divided by the size.

Sort and Compute the Average Excluding Min and Max

We can sort the numbers, and then the first and last numbers are the smallest and largest element respectively. Then we compute the sum of remaining numbers.

1
2
3
4

class Solution:
    def average(self, A: List[int]) -> float:
        A.sort()
        return sum(A[1:-1])/(len(A)-2)

class Solution:
    def average(self, A: List[int]) -> float:
        A.sort()
        return sum(A[1:-1])/(len(A)-2)

Sorting takes O(NLogN) time. We can also take out the min and max from the total sum:

1
2
3
4

class Solution:
    def average(self, A: List[int]) -> float:
        A.sort()
        return (sum(A) - A[0] - A[-1]) / (len(A) - 2)

class Solution:
    def average(self, A: List[int]) -> float:
        A.sort()
        return (sum(A) - A[0] - A[-1]) / (len(A) - 2)

We can also use the pop to remove the first and last element:

1
2
3
4

A.sort()
A.pop()
A.pop(0)
return sum(A) / len(A)

A.sort()
A.pop()
A.pop(0)
return sum(A) / len(A)

The pop(0) takes O(N) time for a list/array in Python.

Find Min, Max and Sum to Compute the Average Excluding Min/Max

We don’t need all numbers to be sorted. Thus, we can just find the min, max and sum in O(N) time:

1

return (sum(A) - max(A) - min(A)) / (len(A) - 2)

return (sum(A) - max(A) - min(A)) / (len(A) - 2)

However, this takes three passes. We can use a single pass to find the max, min and sum:

1
2
3
4
5
6
7
8
9

class Solution:
    def average(self, A: List[int]) -> float:       
        maxv, minv = A[0], A[0]
        s = 0
        for i in A:
            maxv = max(maxv, i)
            minv = min(minv, i)
            s += i
        return (s - maxv - minv) / (len(A) - 2)

class Solution:
    def average(self, A: List[int]) -> float:       
        maxv, minv = A[0], A[0]
        s = 0
        for i in A:
            maxv = max(maxv, i)
            minv = min(minv, i)
            s += i
        return (s - maxv - minv) / (len(A) - 2)

See the same algorithm but in C++: Function to Compute the Average Salary Excluding the Minimum and Maximum Salary

–EOF (The Ultimate Computing & Technology Blog) —