Number of Distinct Averages

Difficulty: Easy | Acceptance: 58.90% | Paid: No Topics: Array, Hash Table, Two Pointers, Sorting

You are given an integer array nums. In one operation, you must:

Choose the minimum and maximum elements from nums. Remove them from nums. Calculate the average of the two removed elements.

The average of two numbers a and b is (a + b) / 2.

For example, the average of 2 and 3 is 2.5, and the average of 2 and 2 is 2.

Return the number of distinct averages calculated using the above process.

Notice that when there is a tie for the minimum or maximum element, any element can be removed.

• Examples
• Constraints
• Sorting and Two Pointers
• Frequency Map (Bucket Sort)
• Brute Force Simulation

Examples

Input: nums = [9,5,7,3,5,3]
Output: 2
Explanation:
1. Remove min=3 and max=9. Average = (3+9)/2 = 6.0. nums = [5,7,5,3].
2. Remove min=3 and max=7. Average = (3+7)/2 = 5.0. nums = [5,5].
3. Remove min=5 and max=5. Average = (5+5)/2 = 5.0. nums = [].
The distinct averages are 6.0 and 5.0. Return 2.

Input: nums = [1,100]
Output: 1
Explanation:
There is only one average to be calculated after removing min=1 and max=100. Average = (1+100)/2 = 50.5.

Constraints

2 <= nums.length <= 100
1 <= nums[i] <= 100

Sorting and Two Pointers

Intuition By sorting the array, the minimum and maximum elements are naturally positioned at the start and end. We can then use two pointers to pair these elements efficiently.

Steps

• Sort the array in ascending order.
• Initialize a set to store distinct averages.
• Use a left pointer at the start and a right pointer at the end.
• While the left pointer is less than the right pointer:
  • Calculate the average of nums[left] and nums[right].
  • Add the average to the set.
  • Increment the left pointer and decrement the right pointer.
• Return the size of the set.

class Solution:
    def distinctAverages(self, nums: list[int]) -> int:
        nums.sort()
        seen = set()
        l, r = 0, len(nums) - 1
        while l < r:
            avg = (nums[l] + nums[r]) / 2
            seen.add(avg)
            l += 1
            r -= 1
        return len(seen)

Complexity

• Time: O(n log n) due to sorting.
• Space: O(n) to store the set of averages.
• Notes: This is the most standard approach for this problem.

Frequency Map (Bucket Sort)

Intuition Since the values in nums are constrained to a small range (1 to 100), we can use a frequency array (bucket sort) to count occurrences. This allows us to find the min and max in O(100) time per operation without sorting the original array.

Steps

• Create a frequency array count of size 101 initialized to 0.
• Populate count based on the numbers in nums.
• Initialize a set to store distinct averages.
• While there are elements remaining (tracked by a total count or by scanning):
  • Find the minimum index min with count[min] > 0.
  • Find the maximum index max with count[max] > 0.
  • Decrement count[min] and count[max].
  • Calculate the average and add it to the set.
• Return the size of the set.

class Solution:
    def distinctAverages(self, nums: list[int]) -> int:
        count = [0] * 101
        for n in nums:
            count[n] += 1
            
        seen = set()
        remaining = len(nums)
        
        while remaining > 0:
            # Find min
            min_val = 0
            for i in range(1, 101):
                if count[i] > 0:
                    min_val = i
                    break
            
            # Find max
            max_val = 0
            for i in range(100, 0, -1):
                if count[i] > 0:
                    max_val = i
                    break
                    
            count[min_val] -= 1
            count[max_val] -= 1
            remaining -= 2
            
            seen.add((min_val + max_val) / 2)
            
        return len(seen)

Complexity

• Time: O(n * C), where C is the range of values (100). Since C is constant, this is effectively O(n).
• Space: O(C) for the frequency array, plus O(n) for the set.
• Notes: This approach avoids sorting and is very efficient for small value ranges.

Brute Force Simulation

Intuition Directly simulate the process described in the problem. In each step, scan the array to find the minimum and maximum elements, remove them, and calculate the average.

Steps

• Convert the array to a mutable list structure.
• Initialize a set for distinct averages.
• While the list is not empty:
  • Find the minimum value in the list.
  • Find the maximum value in the list.
  • Remove the first occurrence of the minimum value.
  • Remove the first occurrence of the maximum value.
  • Calculate the average and add to the set.
• Return the size of the set.

class Solution:
    def distinctAverages(self, nums: list[int]) -> int:
        seen = set()
        while nums:
            mn = min(nums)
            mx = max(nums)
            nums.remove(mn)
            nums.remove(mx)
            seen.add((mn + mx) / 2)
        return len(seen)

Complexity

• Time: O(n²) because finding min/max takes O(n) and removing elements takes O(n), repeated n/2 times.
• Space: O(n) to store the list and the set.
• Notes: This is the least efficient approach but directly follows the problem statement.