Jobs

Interviews

Discussions

Average Salary Excluding the Minimum and Maximum Salary

Easy

Asked by:

3 views

Topics:

Arrays

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.

Try coding it in LeetCode

Average Salary Excluding the Minimum and Maximum Salary

Easy

Asked by:

3 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the minimum and maximum possible size of the `salary` array?
Can the `salary` array contain negative numbers?
Is the input array guaranteed to contain unique integers, as stated in the problem description, or should I account for possible duplicates?
If the input array has fewer than 3 elements, what should the function return?
Should the returned average be an integer or a floating-point number? If floating-point, what level of precision is required?

Brute Force Solution

Approach

To find the average salary excluding the highest and lowest, a brute force approach means we directly simulate the problem's requirements. We will find the maximum and minimum salaries, and then calculate the average of the remaining salaries. This is done by looking at each salary one at a time.

Here's how the algorithm would work step-by-step:

First, find the largest salary among all the salaries.
Next, find the smallest salary among all the salaries.
Then, add up all the salaries, but don't include the largest or smallest salary in the sum.
Count how many salaries were added together (which is the total number of salaries minus two, because we didn't include the largest and smallest).
Finally, divide the sum of the included salaries by the count to get the average.

Code Implementation

def average_salary_excluding_the_minimum_and_maximum_salary(salary):
    maximum_salary = salary[0]
    minimum_salary = salary[0]

    # Find the maximum salary.
    for individual_salary in salary:
        if individual_salary > maximum_salary:
            maximum_salary = individual_salary

    # Find the minimum salary.
    for individual_salary in salary:
        if individual_salary < minimum_salary:
            minimum_salary = individual_salary

    salaries_sum = 0
    number_of_valid_salaries = 0

    # Sum the salaries, excluding the min and max.
    for individual_salary in salary:
        if individual_salary != maximum_salary and individual_salary != minimum_salary:
            salaries_sum += individual_salary
            number_of_valid_salaries += 1

    # Handle the edge case where the list is empty, or all elements are same
    if number_of_valid_salaries == 0:
        return 0

    return salaries_sum / number_of_valid_salaries

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of salaries once to find the maximum salary, which takes O(n) time. It then iterates through the array again to find the minimum salary, also taking O(n) time. Finally, it iterates once more to calculate the sum of salaries excluding the minimum and maximum and to count the number of salaries included, which is another O(n) operation. Thus the total time complexity is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(1) – The algorithm finds the maximum and minimum salaries, calculates a sum, and counts the number of salaries to include in the average. It uses a few variables to store the maximum salary value, minimum salary value, the sum of included salaries, and the count of included salaries. These variables consume a constant amount of extra memory regardless of the number of salaries, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the average salary excluding the highest and lowest, we need to first identify these extreme values. Once identified, we can efficiently compute the sum of the remaining salaries and then divide by the count of those salaries to get the average.

Here's how the algorithm would work step-by-step:

First, find the smallest salary in the set of salaries.
Next, find the largest salary in the set of salaries.
Calculate the sum of all the salaries.
Subtract the smallest salary and the largest salary from the total sum.
Count how many salaries were in the original set, and then subtract 2 (for the smallest and largest salaries we removed).
Divide the adjusted sum by the adjusted count. This result is the average salary, excluding the minimum and maximum.

Code Implementation

def average_salary_excluding_extremes(salary): 
    minimum_salary = min(salary)

    maximum_salary = max(salary)

    salaries_sum = sum(salary)

    # Exclude min and max salaries
    salaries_sum -= (minimum_salary + maximum_salary)

    # Recalculate salary count
    adjusted_salary_count = len(salary) - 2

    # Prevents division by zero
    if adjusted_salary_count == 0:
        return 0

    # Calculate the average salary
    average_salary = salaries_sum / adjusted_salary_count

    return average_salary

Big(O) Analysis

Time Complexity

O(n) – Finding the minimum salary requires iterating through all n salaries once. Similarly, finding the maximum salary also requires iterating through all n salaries. Summing all salaries also takes O(n) time. Finally, the arithmetic operations (subtraction and division) are constant time, O(1). Thus, the dominant factor is iterating through the array, giving a total time complexity of O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a few variables to store the smallest salary, largest salary, the sum of salaries, and the count of salaries. These variables require a constant amount of space regardless of the number of salaries (N) in the input. No additional data structures like arrays or hash maps are used that scale with the input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, or throw an IllegalArgumentException, as the average is undefined for an empty set of salaries.
Array with exactly two elements	After excluding the min and max, no salaries remain, so return 0 as the average of nothing is zero.
Array with identical values	The min and max will be the same value, so after removing them, the average will be the value itself.
Array with very large positive or negative numbers (integer overflow)	Use long to accumulate the sum to prevent integer overflow, especially if salaries are integers.
Array contains zero	The algorithm should work correctly with zero as a valid salary, since it's just a number.
Large input array (performance)	Ensure the solution has a linear time complexity, such as iterating through the array once to find min/max and then calculating the average.
Floating-point precision errors when calculating the average	Use double to store the average to maintain precision, especially when dealing with large salary values.
Array containing only negative values	The algorithm should correctly identify the minimum and maximum (most negative) salary and exclude them.

Null or empty input array

How to Handle:

Return 0, or throw an IllegalArgumentException, as the average is undefined for an empty set of salaries.

Array with exactly two elements

How to Handle:

After excluding the min and max, no salaries remain, so return 0 as the average of nothing is zero.

Array with identical values

How to Handle:

The min and max will be the same value, so after removing them, the average will be the value itself.

Array with very large positive or negative numbers (integer overflow)

How to Handle:

Use long to accumulate the sum to prevent integer overflow, especially if salaries are integers.

Array contains zero

How to Handle:

The algorithm should work correctly with zero as a valid salary, since it's just a number.

Large input array (performance)

How to Handle:

Ensure the solution has a linear time complexity, such as iterating through the array once to find min/max and then calculating the average.

Floating-point precision errors when calculating the average

How to Handle:

Use double to store the average to maintain precision, especially when dealing with large salary values.

Array containing only negative values

How to Handle:

The algorithm should correctly identify the minimum and maximum (most negative) salary and exclude them.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the minimum and maximum possible size of the `salary` array?
Can the `salary` array contain negative numbers?
Is the input array guaranteed to contain unique integers, as stated in the problem description, or should I account for possible duplicates?
If the input array has fewer than 3 elements, what should the function return?
Should the returned average be an integer or a floating-point number? If floating-point, what level of precision is required?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the largest salary among all the salaries.
Next, find the smallest salary among all the salaries.
Then, add up all the salaries, but don't include the largest or smallest salary in the sum.
Count how many salaries were added together (which is the total number of salaries minus two, because we didn't include the largest and smallest).
Finally, divide the sum of the included salaries by the count to get the average.

Code Implementation

def average_salary_excluding_the_minimum_and_maximum_salary(salary):
    maximum_salary = salary[0]
    minimum_salary = salary[0]

    # Find the maximum salary.
    for individual_salary in salary:
        if individual_salary > maximum_salary:
            maximum_salary = individual_salary

    # Find the minimum salary.
    for individual_salary in salary:
        if individual_salary < minimum_salary:
            minimum_salary = individual_salary

    salaries_sum = 0
    number_of_valid_salaries = 0

    # Sum the salaries, excluding the min and max.
    for individual_salary in salary:
        if individual_salary != maximum_salary and individual_salary != minimum_salary:
            salaries_sum += individual_salary
            number_of_valid_salaries += 1

    # Handle the edge case where the list is empty, or all elements are same
    if number_of_valid_salaries == 0:
        return 0

    return salaries_sum / number_of_valid_salaries

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the smallest salary in the set of salaries.
Next, find the largest salary in the set of salaries.
Calculate the sum of all the salaries.
Subtract the smallest salary and the largest salary from the total sum.
Count how many salaries were in the original set, and then subtract 2 (for the smallest and largest salaries we removed).
Divide the adjusted sum by the adjusted count. This result is the average salary, excluding the minimum and maximum.

Code Implementation

def average_salary_excluding_extremes(salary): 
    minimum_salary = min(salary)

    maximum_salary = max(salary)

    salaries_sum = sum(salary)

    # Exclude min and max salaries
    salaries_sum -= (minimum_salary + maximum_salary)

    # Recalculate salary count
    adjusted_salary_count = len(salary) - 2

    # Prevents division by zero
    if adjusted_salary_count == 0:
        return 0

    # Calculate the average salary
    average_salary = salaries_sum / adjusted_salary_count

    return average_salary

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, or throw an IllegalArgumentException, as the average is undefined for an empty set of salaries.
Array with exactly two elements	After excluding the min and max, no salaries remain, so return 0 as the average of nothing is zero.
Array with identical values	The min and max will be the same value, so after removing them, the average will be the value itself.
Array with very large positive or negative numbers (integer overflow)	Use long to accumulate the sum to prevent integer overflow, especially if salaries are integers.
Array contains zero	The algorithm should work correctly with zero as a valid salary, since it's just a number.
Large input array (performance)	Ensure the solution has a linear time complexity, such as iterating through the array once to find min/max and then calculating the average.
Floating-point precision errors when calculating the average	Use double to store the average to maintain precision, especially when dealing with large salary values.
Array containing only negative values	The algorithm should correctly identify the minimum and maximum (most negative) salary and exclude them.

Null or empty input array

How to Handle:

Return 0, or throw an IllegalArgumentException, as the average is undefined for an empty set of salaries.

Array with exactly two elements

How to Handle:

After excluding the min and max, no salaries remain, so return 0 as the average of nothing is zero.

Array with identical values

How to Handle:

The min and max will be the same value, so after removing them, the average will be the value itself.

Array with very large positive or negative numbers (integer overflow)

How to Handle:

Use long to accumulate the sum to prevent integer overflow, especially if salaries are integers.

Array contains zero

How to Handle:

The algorithm should work correctly with zero as a valid salary, since it's just a number.

Large input array (performance)

How to Handle:

Ensure the solution has a linear time complexity, such as iterating through the array once to find min/max and then calculating the average.

Floating-point precision errors when calculating the average

How to Handle:

Use double to store the average to maintain precision, especially when dealing with large salary values.

Array containing only negative values

How to Handle:

The algorithm should correctly identify the minimum and maximum (most negative) salary and exclude them.