Watch 10 video solutions for Number of Distinct Averages, a easy level problem involving Array, Hash Table, Two Pointers. This walkthrough by Developer Docs has 800 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem Overview: You are given an even-length integer array. In each step, remove the smallest and largest numbers, compute their average, and store it. Repeat until the array is empty. The goal is to return how many distinct averages appear during this process.
Approach 1: Using Hash Maps / Hash Set (O(n log n) time, O(n) space)
This approach focuses on tracking unique averages using a hash-based structure. First, sort the array so the smallest and largest values can be accessed easily. Then iterate using two pointers: one at the beginning and one at the end of the array. For every pair, compute the average using (nums[left] + nums[right]) / 2 and insert the result into a hash set. Because sets store only unique values, duplicates are automatically removed. Continue moving the pointers inward until all elements are processed.
The key idea is that the order of removal does not affect the result once the array is sorted. Every step always combines the smallest and largest remaining elements. The hash structure guarantees O(1) average insertion and lookup, so counting distinct averages becomes straightforward. This method works well for general hash table problems where uniqueness needs to be tracked efficiently.
Approach 2: Using Sorting and Two Pointers (O(n log n) time, O(n) space)
Another clean solution relies on sorting and the classic two-pointer technique. After sorting the array, place one pointer at the start and another at the end. Each iteration forms a pair consisting of the minimum and maximum remaining values. Compute their sum or average and store it in a set. Move the left pointer forward and the right pointer backward until they cross.
The sorting step dominates the runtime with O(n log n), while the pairing process itself runs in O(n). This approach highlights a common pattern in two pointers and sorting problems: sort first, then process symmetric elements from both ends. It avoids repeated scanning for minimum or maximum values and keeps the implementation compact.
Recommended for interviews: Interviewers usually expect the sorting + two-pointer solution. It demonstrates recognition of a symmetric pairing pattern and efficient iteration across the array. Mentioning a hash set to track unique averages shows awareness of constant-time lookups. A brute-force idea (repeatedly scanning for min and max) shows baseline understanding, but the sorted two-pointer solution shows stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set with Pair Tracking | O(n log n) | O(n) | General solution when you need to track distinct averages efficiently |
| Sorting + Two Pointers | O(n log n) | O(n) | Preferred interview approach when pairing smallest and largest elements |