algoadvance

Leetcode 1491. Average Salary Excluding the Minimum and Maximum Salary

Problem Statement

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.

Example:

Input: salary = [4000, 3000, 1000, 2000]
Output: 2500.00000
Explanation: Minimum salary: 1000, maximum salary: 4000
Average salary: (2000+3000)/2 = 2500

Clarifying Questions

1. Q: What is the size range of the salary array?
   • A: The number of elements in the array is at least 3.
2. Q: Are the salaries unique?
   • A: Yes, all salaries are unique.
3. Q: Should the output be a floating-point number?
   • A: Yes, the output should be represented as a floating-point number.

Strategy

1. First, find the minimum and maximum salaries in the array.
2. Sum all salaries.
3. Subtract the minimum and maximum salaries from the sum.
4. Compute the average by dividing the adjusted sum by the number of salaries excluding the minimum and maximum (i.e., total number of salaries - 2).

Code

#include <iostream>
#include <vector>
#include <numeric> // for accumulate
#include <algorithm> // for min_element and max_element

double averageSalaryExcludingMinMax(const std::vector<int>& salary) {
    int minSalary = *std::min_element(salary.begin(), salary.end());
    int maxSalary = *std::max_element(salary.begin(), salary.end());

    int totalSum = std::accumulate(salary.begin(), salary.end(), 0);

    // Calculate the adjusted sum by excluding the minimum and maximum salaries
    int adjustedSum = totalSum - minSalary - maxSalary;

    // Calculate the average excluding the smallest and largest salaries
    int n = salary.size() - 2;
    return static_cast<double>(adjustedSum) / n;
}

int main() {
    std::vector<int> salary = {4000, 3000, 1000, 2000};
    double result = averageSalaryExcludingMinMax(salary);
    std::cout << "Average Salary Excluding Min and Max: " << result << std::endl;
    return 0;
}

Time Complexity

• Finding Min and Max Salary: O(N) where N is the number of elements in the array.
• Accumulating the Sum: O(N).
• Overall, the time complexity is O(N) since each of the above operations iterates through the array once.

Space Complexity

• We use a constant amount of extra space, so the space complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?