Average Salary Excluding Min and Max: Single Pass Array Scan

You are given an array of unique salaries. Your task is to compute the average salary, but with a twist: exclude both the minimum and maximum salaries before calculating. This is LeetCode 1491: Average Salary Excluding the Minimum and Maximum Salary, an easy problem that tests your ability to process an array efficiently without resorting to sorting when you do not need to.

Why this problem matters

This problem is simple on the surface, but it introduces a concept that matters a lot in harder problems: doing multiple things in a single pass. Most beginners sort the array, drop the first and last elements, then average the rest. That works, but it is O(n log n) when an O(n) solution exists. Recognizing that you can find the min, max, and sum all at once is the kind of optimization that separates efficient code from correct-but-slow code.

The pattern also comes up in real-world data processing. Think about trimmed means in statistics, where you exclude outliers before averaging. Or consider a system that ranks items but discards the highest and lowest scores (like Olympic judging). The underlying operation is always the same: scan the data, identify the extremes, and compute a result that excludes them.

The key insight

You do not need to sort the array. Sorting costs O(n log n), but finding the minimum, maximum, and total sum only requires a single pass through the data. Once you have all three values, the average of the remaining elements is (total - min - max) / (n - 2). That is three operations tracked simultaneously in one loop, which gives you O(n) time and O(1) space.

The trick is to realize that you never need to know which elements are the min and max. You only need their values. Once you subtract them from the total sum, whatever remains is the sum of the middle elements. Dividing by n - 2 gives the average.

The solution

def average(salary):
    min_s = min(salary)
    max_s = max(salary)
    return (sum(salary) - min_s - max_s) / (len(salary) - 2)

Here is what each piece does:

1. min(salary) scans the array once to find the smallest value.
2. max(salary) scans the array once to find the largest value.
3. sum(salary) scans the array once to compute the total.
4. Subtract min_s and max_s from the total, then divide by len(salary) - 2.

Python's built-in min, max, and sum each run in O(n), so this is three passes total. Still O(n), and the code is clean and readable. If you want a true single-pass version, you can combine all three into one loop (shown in the building blocks section below).

Visual walkthrough

Each step is doing constant work: tracking two variables (min and max), computing a sum, and performing one subtraction and one division at the end. No nested loops, no sorting, no extra data structures.

Complexity analysis

The single-pass approach visits each element a constant number of times (once for min, once for max, once for sum, or all at once in a combined loop). Space is O(1) because you only store the running min, max, and sum.

The sorting approach sorts the array first, then sums elements from index 1 to n-2. Sorting dominates at O(n log n). Both approaches use O(1) extra space (assuming in-place sorting), but the single-pass version is faster.

For this easy problem, the difference rarely matters in practice. But the habit of choosing O(n) over O(n log n) when possible pays off in harder problems where the input size is large and the time limit is tight.

The building blocks

1. Finding min and max in one pass

Instead of calling min() and max() separately, you can track both in a single loop:

def find_min_max(arr):
    lo = arr[0]
    hi = arr[0]
    for val in arr:
        if val < lo:
            lo = val
        if val > hi:
            hi = val
    return lo, hi

This is the same work that Python's built-in functions do internally, but combined into one pass. The pattern appears whenever you need to extract multiple aggregate values from an array without sorting. Problems like Third Maximum Number and Kth Largest Element build on this same scan-and-track idea.

2. Computing a filtered average

Once you have the values to exclude, computing the filtered average is a matter of subtracting them from the total and adjusting the count:

def filtered_average(arr, exclude_min, exclude_max):
    total = sum(arr)
    return (total - exclude_min - exclude_max) / (len(arr) - 2)

This pattern generalizes. If you need to exclude the top k and bottom k values (a trimmed mean), you sort and slice. But when you are only excluding one element from each end, subtraction is cheaper than sorting. The same subtract-and-adjust approach shows up in problems where you need the sum of a subset defined by exclusion rather than inclusion.

Edge cases

Before submitting, make sure your solution handles these:

• Exactly three salaries [1000, 2000, 3000]: after excluding min and max, only one value remains. The average is just that middle value.
• All salaries close together [1000, 1001, 1002]: the average of the middle element is 1001. No precision issues since the values are small integers.
• Large salary values [10^6, 10^6 - 1, 10^6 - 2]: make sure your sum does not overflow in languages with fixed-size integers. Python handles big integers natively, but in Java or C++ you may need a long.
• Minimum array size the problem guarantees at least 3 elements, so n - 2 is always at least 1. You never divide by zero.
• Salaries are already sorted [1000, 2000, 3000, 4000]: the algorithm does not assume any ordering, so it works the same regardless of input arrangement.

From understanding to recall

You have read through the solution and it makes sense. Find min, find max, subtract both from the total, divide by n - 2. Four lines of code. Clean and fast.

But the value of this problem is not the solution itself. It is the pattern: scanning an array to extract aggregate values without sorting. This same pattern appears in dozens of other problems. Third Maximum Number asks you to track three values instead of two. Best Time to Buy and Sell Stock asks you to track a running minimum while computing a running maximum difference. The core mechanic is always the same: walk through the array once, maintain a few variables, and produce the result at the end.

Spaced repetition helps you internalize this scan-and-track pattern so it fires automatically. You practice writing the single-pass min/max/sum loop from scratch at increasing intervals. After a few rounds, you see "find extremes and compute a derived value" and the code comes out without hesitation.

Related posts

• Two Sum - Single pass array processing with a complementary lookup
• Contains Duplicate - Array scanning patterns with set-based tracking
• Maximum Subarray - Single pass optimization using Kadane's algorithm

This problem is a clean introduction to the scan-and-track pattern. The solution is short, but the idea behind it scales to much harder problems. If you want to make the pattern automatic, practice it with spaced repetition until the loop structure is second nature.