You are given a 0-indexed integer array nums of even length.
As long as nums is not empty, you must repetitively:
nums and remove it.nums and remove it.The average of two numbers a and b is (a + b) / 2.
2 and 3 is (2 + 3) / 2 = 2.5.Return the number of distinct averages calculated using the above process.
Note that when there is a tie for a minimum or maximum number, any can be removed.
Example 1:
Input: nums = [4,1,4,0,3,5] Output: 2 Explanation: 1. Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3]. 2. Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = [4,3]. 3. Remove 3 and 4, and the average is (3 + 4) / 2 = 3.5. Since there are 2 distinct numbers among 2.5, 2.5, and 3.5, we return 2.
Example 2:
Input: nums = [1,100] Output: 1 Explanation: There is only one average to be calculated after removing 1 and 100, so we return 1.
Constraints:
2 <= nums.length <= 100nums.length is even.0 <= nums[i] <= 100In #2465 Number of Distinct Averages, the key idea is to repeatedly pair the smallest and largest values and compute their average. A practical way to approach this is by first sorting the array. Once sorted, you can use the two-pointer technique: one pointer at the beginning (smallest element) and another at the end (largest element).
For each step, compute the average of the two numbers and store it in a structure that only keeps unique values, such as a set. Then move the left pointer forward and the right pointer backward until all pairs are processed. Since duplicates are automatically ignored in a set, the final size of the set represents the number of distinct averages.
The main cost comes from sorting the array. After sorting, the pairing process runs in linear time. This approach is efficient and commonly used in interviews because it combines sorting, two pointers, and hashing for uniqueness.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Two Pointers with Hash Set | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Try sorting the array.
Store the averages being calculated, and find the distinct ones.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting allows you to easily access the smallest and largest elements using two pointers. This simplifies pairing elements from opposite ends of the array. It also ensures each step processes the correct min–max pair.
Problems like Number of Distinct Averages are common in coding interviews because they test fundamentals such as sorting, two-pointer techniques, and hash sets. While the exact question may vary, similar patterns frequently appear in technical interviews.
A hash set is the best choice because it automatically stores only unique values. As you compute averages from each pair, inserting them into the set ensures duplicates are ignored. This makes counting distinct averages straightforward.
The optimal approach is to sort the array and use two pointers to pair the smallest and largest elements. For each pair, compute the average and store it in a set to track unique values. The size of the set gives the number of distinct averages.