#2465

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Distinct Averages

Calculate the number of unique averages formed by repeatedly pairing smallest and largest elements efficiently using hashing.

array hash table two pointers sorting

Problem Statement

You are given an even-length integer array nums. Repeatedly remove the smallest and largest elements and compute their average until the array is empty.

Return the number of distinct averages obtained from these pairings. Each average is calculated as (a + b) / 2 for removed elements a and b.

Examples

Example 1

Input: nums = [4,1,4,0,3,5]

Output: 2

Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3].
Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = [4,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

There is only one average to be calculated after removing 1 and 100, so we return 1.

Constraints

2 <= nums.length <= 100
nums.length is even.
0 <= nums[i] <= 100

Solution Approach

Sort and Two-Pointer Pairing

Sort nums to simplify selecting the smallest and largest elements. Use left and right pointers to traverse from both ends while calculating each average and adding it to a hash set.

Hash Set for Distinct Tracking

Store each computed average in a hash set to automatically handle duplicates. The final count of unique averages equals the size of this set.

Iterative Removal Until Empty

Move the two pointers inward after each pairing until they meet. This ensures every number contributes to an average and all pairs are considered for distinct counting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting plus O(n) for scanning and averaging pairs. Space complexity is O(n) in the worst case for storing distinct averages in the hash set.

What Interviewers Usually Probe

Candidate quickly identifies the two-pointer pattern after sorting.
Candidate suggests using a hash set to track distinct averages without recounting.
Candidate properly handles edge cases where averages repeat multiple times.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the array and mispairing elements.
Overwriting averages instead of storing in a set, losing distinct counts.
Incorrectly handling integer division versus floating-point averages.

Follow-up variants

Count distinct sums instead of averages for paired elements.
Apply the method to odd-length arrays with one unpaired element ignored.
Compute averages using a sliding window instead of pair removal.

FAQ

What is the main pattern for Number of Distinct Averages?

The main pattern is array scanning with two pointers after sorting and using a hash set to count distinct averages.

Can this method handle repeated numbers correctly?

Yes, the hash set ensures that repeated averages are only counted once, so duplicates do not affect the final count.

What is the optimal time complexity?

Sorting gives O(n log n) and scanning pairs gives O(n), so total time complexity is O(n log n).

How does integer division affect the result?

Use floating-point division to ensure averages are accurate; integer division may merge distinct averages incorrectly.

Is sorting always necessary for this problem?

Sorting simplifies pairing smallest and largest elements; without sorting, you need a more complex structure to track min and max efficiently.

terminal

Solution

Solution 1: Sorting

The problem requires us to find the minimum and maximum values in the array $nums$ each time, delete them, and then calculate the average of the two deleted numbers. Therefore, we can first sort the array $nums$, then take the first and last elements of the array each time, calculate their sum, use a hash table or array $cnt$ to record the number of times each sum appears, and finally count the number of different sums.

1

2

3

4

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        return len(set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)))

Solution 2

#### Python3

1

2

3

4

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        return len(set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)))

Solution 3

#### Rust

1

2

3

4

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        return len(set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)))

Continue Practicing

#2441 largest positive integer that exists with its negative #2491 divide players into teams of equal skill #2122 recover the original array