Average Salary Excluding the Minimum and Maximum Salary - Video Solutions

Problem Overview: You receive an array of unique salaries. The task is to compute the average salary after removing the smallest and largest values. Only the remaining elements contribute to the final average.

Approach 1: Sorting and Slicing (Time: O(n log n), Space: O(1) or O(n) depending on language)

Sort the salary array using a standard sorting algorithm. After sorting, the smallest value appears at index 0 and the largest at index n-1. Ignore those two elements and compute the average of the remaining slice. Most languages allow easy slicing such as salary[1:-1]. This approach is simple and readable, but sorting introduces an unnecessary O(n log n) cost when the order of elements is irrelevant.

Approach 2: Single Traversal (Time: O(n), Space: O(1))

Iterate through the array once while tracking three values: the total sum, the minimum salary, and the maximum salary. During each step, update the running sum and compare the current value against the tracked min and max. After the loop finishes, subtract the min and max from the sum and divide by n - 2. This avoids sorting entirely and processes the array in linear time. The approach relies on simple operations over an array, making it both optimal and memory efficient.

The key insight is that you don't need the salaries in order. You only need the smallest and largest values, which can be tracked during iteration. This transforms the problem from a sorting task into a simple aggregation pass.

Recommended for interviews: The single traversal approach. Sorting demonstrates correctness but wastes time complexity. Tracking sum, min, and max in one pass shows stronger understanding of array processing and algorithmic optimization.