Minimum Average of Smallest and Largest Elements - Solution & Explanation

Problem Overview: You are given an integer array. Repeatedly take the smallest and largest remaining elements, compute their average (a + b) / 2, and track the minimum average among all such pairs. Each step removes both elements from consideration. The goal is to return the smallest average produced during this process.

The key observation: pairing the smallest and largest values naturally happens when the array is ordered. Once sorted, the smallest element sits at the left end and the largest at the right end, making the pairing step trivial.

Approach 1: Sorting + Two Pointers (O(n log n) time, O(1) extra space)

Sort the array first. After sorting, use two pointers: left starting at index 0 and right at the last index. At each step, compute the average of nums[left] and nums[right], update the running minimum, then move both pointers inward (left++, right--). Sorting guarantees that every iteration pairs the current smallest and largest remaining elements exactly as the problem requires. The dominant cost is sorting at O(n log n), while the two‑pointer scan runs in O(n). Extra space stays O(1) if sorting is done in place.

This approach relies on ideas from sorting and two pointers. Once the array is ordered, the algorithm becomes a simple linear sweep.

Approach 2: Min Heap + Max Heap (O(n log n) time, O(n) space)

Another way to simulate the process is by maintaining two heaps: a min heap to retrieve the smallest element and a max heap to retrieve the largest element. Insert all numbers into both structures. In each step, extract the minimum from the min heap and the maximum from the max heap, compute their average, and update the minimum result. This directly mirrors the "remove smallest and largest" rule.

Heap operations such as push and pop take O(log n) time, so building and processing the heaps leads to overall O(n log n) time complexity with O(n) extra space. This technique uses concepts from heap data structures and works well when you need dynamic access to extremes.

Recommended for interviews: The sorting + two pointers approach is what most interviewers expect. It directly models the pairing logic and keeps the implementation small and readable. Showing the heap approach demonstrates understanding of priority queues, but the sorted two‑pointer solution is cleaner and uses less memory.

The core idea across both methods is the same: always combine the smallest and largest remaining elements. Sorting simply provides the most efficient and straightforward way to enforce that pairing.