Number of Distinct Averages

Number of Distinct Averages

What is this problem about?

The Number of Distinct Averages problem gives you an even-length array. Repeatedly remove the minimum and maximum elements, compute their average, and count how many distinct averages are produced. This easy coding problem uses a two-pointer approach on a sorted array.

Why is this asked in interviews?

Amazon asks this to test sorting with two-pointer pairing and set-based distinctness tracking. It validates clean algorithm design for a simple repetitive operation. The array, hash table, sorting, and two pointers interview pattern is demonstrated here concisely.

Algorithmic pattern used

Sort + two pointers + set. Sort the array. Use a left pointer at index 0 and a right pointer at n-1. Each step: compute average of arr[left] + arr[right] (or just sum, since we only care about distinctness — compare sums instead of floats). Add to a set. Advance both pointers inward. Return the set size.

Example explanation

Array: [4, 1, 4, 3, 2]. Sort: [1,2,3,4,4].

• Pointers: left=0(1), right=4(4). Sum=5. Set={5}.
• left=1(2), right=3(4). Sum=6. Set={5,6}.
• left=2(3), right=2(3). Wait — single middle element, but length is 5 (odd). For even-length arrays only: [4,1,4,2], sort=[1,2,4,4]. (1+4)=5, (2+4)=6. Distinct = 2.

Common mistakes candidates make

• Computing actual averages as floats (causes precision issues — use sums for distinctness).
• Not sorting before applying two pointers.
• Off-by-one: stopping when left > right (not left == right for even-length).
• Using a list instead of a set (counting duplicates as distinct).

Interview preparation tip

"Pair minimum with maximum" problems always benefit from sorting first, then using two pointers from both ends. Using integer sums instead of float averages avoids precision issues. After sorting, the two-pointer approach naturally pairs the smallest with the largest, then the second-smallest with the second-largest, etc. Practice this pattern on "minimum sum of paired elements," "maximum pair sum," and related pairing problems.