Problem Description

You are given an integer array nums with an even number of elements (0-indexed).

Your task is to repeatedly perform the following operations until the array is empty:

1. Find and remove the minimum number from nums
2. Find and remove the maximum number from nums
3. Calculate the average of these two removed numbers using the formula (a + b) / 2

You need to return the total number of distinct averages that you calculate through this entire process.

For example, if you have nums = [4, 1, 4, 0, 3, 5]:

• First iteration: Remove min=0 and max=5, average = (0 + 5) / 2 = 2.5
• Second iteration: Remove min=1 and max=4, average = (1 + 4) / 2 = 2.5
• Third iteration: Remove min=3 and max=4, average = (3 + 4) / 2 = 3.5
• The distinct averages are {2.5, 3.5}, so the answer is 2

Note that when there are multiple occurrences of the minimum or maximum value, you can remove any one of them.

The solution approach sorts the array first, which allows us to pair up elements from the beginning and end of the sorted array. Since we're counting distinct averages and the average depends only on the sum (a + b), we can track distinct sums instead. The code uses nums[i] + nums[-i - 1] to pair the i-th smallest with the i-th largest element, iterating through half the array length.

Intuition

The key insight is recognizing that when we repeatedly remove the minimum and maximum elements from an array, we're essentially pairing up the smallest elements with the largest elements.

Think about what happens after sorting the array. The smallest element will naturally pair with the largest element, the second smallest with the second largest, and so on. This pattern continues until all elements are paired up.

For example, with a sorted array [1, 2, 3, 4, 5, 6]:

• First removal: min=1, max=6 → pair (1, 6)
• Second removal: min=2, max=5 → pair (2, 5)
• Third removal: min=3, max=4 → pair (3, 4)

This is exactly what would happen if we sorted first and then paired elements from opposite ends of the array!

Since we only care about distinct averages, and the average is (a + b) / 2, two pairs will have the same average only if they have the same sum. Therefore, instead of calculating and storing the actual averages (which involves division), we can simply track the distinct sums of pairs.

By sorting the array first, we can efficiently access these pairs using two pointers - one from the start (i) and one from the end (-i-1). We iterate through half the array length since each iteration processes one pair, and we have n/2 pairs total for an array of length n.

This transforms the problem from repeatedly finding min/max (which would be O(n²) overall) to a simple O(n log n) sorting followed by O(n) traversal.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution implements the sorting approach to efficiently find the distinct averages:

1. Sort the array: First, we sort nums in ascending order. This arranges elements so that we can easily access minimum and maximum values without repeated searching.

2. Pair elements from opposite ends: After sorting, we use a list comprehension to pair elements:

   • nums[i] gives us the i-th element from the start (smaller values)
   • nums[-i - 1] gives us the i-th element from the end (larger values)
   • We calculate the sum nums[i] + nums[-i - 1] for each pair

3. Iterate through half the array: The range is range(len(nums) >> 1), where >> 1 is a bitwise right shift operation equivalent to dividing by 2. Since the array has even length and we process two elements per iteration, we only need to iterate n/2 times.

4. Use a set to track distinct sums: The list comprehension generates all sums, and wrapping it with set() automatically removes duplicates. Since two pairs have the same average only if they have the same sum, counting distinct sums is equivalent to counting distinct averages.

5. Return the count: Finally, len() gives us the number of distinct sums, which equals the number of distinct averages.

Time Complexity: O(n log n) for sorting, where n is the length of the array. The subsequent operations are O(n).

Space Complexity: O(n) for storing the set of distinct sums.

The elegance of this solution lies in recognizing that after sorting, the pairing pattern is deterministic, allowing us to avoid the repeated min/max searches that would be required in a naive simulation approach.

Example Walkthrough

Let's trace through the solution with nums = [1, 5, 2, 3, 8, 6].

Step 1: Sort the array

• Original: [1, 5, 2, 3, 8, 6]
• After sorting: [1, 2, 3, 5, 6, 8]

Step 2: Pair elements from opposite ends

Since the array has 6 elements, we'll iterate 3 times (len(nums) >> 1 = 6 >> 1 = 3):

• i = 0:

  • nums[0] = 1 (1st from start)
  • nums[-0-1] = nums[-1] = 8 (1st from end)
  • Sum = 1 + 8 = 9

• i = 1:

  • nums[1] = 2 (2nd from start)
  • nums[-1-1] = nums[-2] = 6 (2nd from end)
  • Sum = 2 + 6 = 8

• i = 2:

  • nums[2] = 3 (3rd from start)
  • nums[-2-1] = nums[-3] = 5 (3rd from end)
  • Sum = 3 + 5 = 8

Step 3: Collect distinct sums

• All sums: [9, 8, 8]
• Convert to set to remove duplicates: {9, 8}
• Count of distinct sums = 2

Verification with original process: If we followed the problem's original steps:

1. Remove min=1, max=8 → average = (1+8)/2 = 4.5
2. Remove min=2, max=6 → average = (2+6)/2 = 4.0
3. Remove min=3, max=5 → average = (3+5)/2 = 4.0

Distinct averages: {4.5, 4.0} → count = 2 ✓

The solution correctly identifies 2 distinct averages by tracking distinct sums instead of calculating the actual averages.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which uses Python's Timsort algorithm with O(n × log n) complexity. The subsequent operations include iterating through half the array (range(len(nums) >> 1)) which is O(n/2) = O(n), and creating a set from the generator expression which is also O(n) in the worst case. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

The space complexity is O(n). The sorting operation in Python can use up to O(n) auxiliary space in the worst case. Additionally, the set comprehension creates a set that can contain at most n/2 elements (since we iterate n/2 times), which requires O(n) space. The generator expression itself doesn't create additional space as it's evaluated lazily within the set constructor. Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Pairing Logic with Negative Indexing

A common mistake is incorrectly pairing elements after sorting, especially when using negative indices. Developers might write:

• nums[i] + nums[-i] (incorrect) instead of nums[i] + nums[-i - 1] (correct)

The issue is that when i = 0, nums[-0] equals nums[0], causing the first element to be paired with itself rather than with the last element.

Solution: Always use nums[-i - 1] to properly access the i-th element from the end. Verify with a simple example:

# For array [1, 2, 3, 4] after sorting:
# i=0: nums[0]=1 pairs with nums[-0-1]=nums[-1]=4 ✓
# i=1: nums[1]=2 pairs with nums[-1-1]=nums[-2]=3 ✓

2. Using Division for Averages Instead of Sums

Some might calculate actual averages using (nums[i] + nums[-i - 1]) / 2 and store them in the set. While this works, it introduces unnecessary floating-point operations and potential precision issues.

Solution: Since all averages are divided by the same constant (2), comparing sums is sufficient for determining distinctness. Keep the implementation simple by storing sums:

# Instead of:
averages = set((nums[i] + nums[-i - 1]) / 2 for i in range(len(nums) // 2))

# Use:
sums = set(nums[i] + nums[-i - 1] for i in range(len(nums) // 2))

3. Forgetting to Handle the Even-Length Constraint

The problem guarantees an even number of elements, but developers might write defensive code for odd-length arrays, adding unnecessary complexity. Conversely, if this constraint changes in a variant problem, the current solution would fail silently.

Solution: Trust the problem constraints for contest/interview scenarios, but in production code, consider adding an assertion:

assert len(nums) % 2 == 0, "Array must have even number of elements"

4. Using Bitwise Operations Without Understanding

The code uses len(nums) >> 1 for division by 2. While this is a valid optimization, using it without understanding can lead to errors when modifying the code or when dealing with negative numbers in other contexts.

Solution: For clarity, especially in interviews, consider using len(nums) // 2 unless specifically optimizing for performance. Both achieve the same result for positive integers, but // is more immediately readable.