Number of Distinct Averages
EasyPrompt
You are given a 0-indexed integer array nums of even length.
As long as nums is not empty, you must repetitively:
- Find the minimum number in
numsand remove it. - Find the maximum number in
numsand remove it. - Calculate the average of the two removed numbers.
The average of two numbers a and b is (a + b) / 2.
- For example, the average of
2and3is(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.lengthis even.0 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem statement. In a loop, it repeatedly finds the minimum and maximum values in the current collection of numbers, calculates their average, and then removes them. A HashSet is used to keep track of the unique averages encountered.
Algorithm
- Convert the input array
numsinto aList<Integer>. - Initialize an empty
Set<Double>calledaverages. - Loop while the list is not empty:
- Find the minimum value (
minVal) in the list. - Find the maximum value (
maxVal) in the list. - Calculate
avg = (minVal + maxVal) / 2.0. - Add
avgto theaveragesset. - Remove one occurrence of
minValfrom the list. - Remove one occurrence of
maxValfrom the list.
- Find the minimum value (
- Return the size of the
averagesset.
Walkthrough
We first convert the input array nums into a List (like ArrayList) to facilitate the easy removal of elements. A HashSet<Double> is initialized to store the distinct averages. The main logic is a while loop that continues as long as the list is not empty. Inside the loop, we find the minimum and maximum elements using a linear scan or a helper function like Collections.min() and Collections.max(). The average of these two values is calculated and added to our HashSet, which automatically handles duplicates. Finally, we remove one instance of the minimum value and one instance of the maximum value from the list. It's important to remove by value (e.g., list.remove(Integer.valueOf(minVal))) to avoid issues with duplicate numbers and index-based removal. After the loop terminates, the size of the HashSet gives the number of distinct averages.
import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int distinctAverages(int[] nums) { List<Integer> list = new ArrayList<>(); for (int num : nums) { list.add(num); } Set<Double> averages = new HashSet<>(); while (!list.isEmpty()) { int minVal = Collections.min(list); int maxVal = Collections.max(list); double avg = (minVal + maxVal) / 2.0; averages.add(avg); list.remove(Integer.valueOf(minVal)); list.remove(Integer.valueOf(maxVal)); } return averages.size(); }}Complexity
Time
O(N^2), where N is the length of `nums`. In each of the N/2 iterations, finding the min/max and removing elements from the list takes O(K) time, where K is the current size of the list. This leads to a complexity of `O(N + (N-2) + ... + 2)`, which is `O(N^2)`.
Space
O(N) to store the list of numbers and the set of averages, where N is the length of `nums`.
Trade-offs
Pros
Very intuitive and directly follows the problem description.
Easy to implement.
Cons
Inefficient due to repeated linear scans to find min/max and remove elements.
A more efficient approach involves sorting the array first. Once sorted, the smallest element is always at the beginning of the remaining portion of the array, and the largest is at the end. We can use two pointers, one at the start and one at the end, moving inwards to pair the minimum and maximum elements.
Algorithm
- Sort the input array
nums. - Initialize an empty
Set<Double>calledaverages. - Initialize two pointers:
left = 0andright = nums.length - 1. - Loop while
left < right:- Calculate
avg = (nums[left] + nums[right]) / 2.0. - Add
avgto theaveragesset. - Increment
leftand decrementright.
- Calculate
- Return the size of the
averagesset.
Walkthrough
The key insight is that the process of repeatedly taking the minimum and maximum element is equivalent to pairing the i-th smallest element with the i-th largest element. First, we sort the input array nums in ascending order. We initialize a HashSet<Double> to store the distinct averages. Two pointers, left and right, are initialized to the start (0) and end (nums.length - 1) of the sorted array, respectively. We loop as long as left < right. In each iteration, the current minimum is nums[left] and the current maximum is nums[right]. We calculate their average and add it to the HashSet. We then "remove" these elements by moving the pointers inward: left++ and right--. The loop continues until the pointers meet or cross, at which point all numbers have been paired. The final answer is the size of the HashSet.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int distinctAverages(int[] nums) { Arrays.sort(nums); Set<Double> averages = new HashSet<>(); int left = 0; int right = nums.length - 1; while (left < right) { double avg = (nums[left] + nums[right]) / 2.0; averages.add(avg); left++; right--; } return averages.size(); }}Complexity
Time
O(N log N), dominated by the sorting step. The two-pointer traversal is `O(N)`.
Space
O(N) for the `HashSet`. Some sorting algorithms might use `O(log N)` or `O(N)` auxiliary space, but `Arrays.sort` in Java for primitives has an average space complexity of `O(log N)`. The `HashSet` can store up to N/2 elements, so the dominant factor is `O(N)`.
Trade-offs
Pros
Significantly more efficient than the simulation approach.
The logic is clean and easy to follow.
Cons
The
O(N log N)time complexity from sorting is not the absolute fastest possible, given the constraints.It modifies the input array, which might not be desirable in some contexts (though a copy could be made).
This approach leverages the constraint that the numbers in the array are small (0 to 100). Instead of a general-purpose sort, we can use a frequency array (or counting sort) to count the occurrences of each number. Then, we can use two pointers on this frequency array to find the current min and max values to pair up.
Algorithm
- Create a frequency array
countsof size 101, initialized to zeros. - Iterate through
numsand incrementcounts[num]for each number. - Initialize an empty
Set<Double>averages. - Initialize two pointers:
minVal = 0andmaxVal = 100. - Loop
nums.length / 2times:- Increment
minValwhilecounts[minVal]is 0. - Decrement
maxValwhilecounts[maxVal]is 0. - Calculate
avg = (minVal + maxVal) / 2.0. - Add
avgto theaveragesset. - Decrement
counts[minVal]andcounts[maxVal].
- Increment
- Return the size of the
averagesset.
Walkthrough
Since 0 <= nums[i] <= 100, we can create an integer array counts of size 101. We iterate through the input nums and populate counts, where counts[x] stores the frequency of the number x. Similar to the sorting approach, we use two pointers, minVal and maxVal, initialized to 0 and 100 respectively. These pointers will scan the counts array. We loop nums.length / 2 times to form all the pairs. In each iteration, we advance minVal from its current position until we find a number that exists (i.e., counts[minVal] > 0). Similarly, we move maxVal downwards until we find an existing number (counts[maxVal] > 0). These minVal and maxVal are the current smallest and largest numbers. We calculate their average and add it to a HashSet. We then decrement their counts in the counts array to mark them as "used". This process is repeated until all pairs are formed. This method avoids the O(N log N) sorting cost and achieves linear time complexity.
import java.util.HashSet;import java.util.Set; class Solution { public int distinctAverages(int[] nums) { int[] counts = new int[101]; for (int num : nums) { counts[num]++; } Set<Double> averages = new HashSet<>(); int minVal = 0; int maxVal = 100; int pairsFound = 0; int n = nums.length; while (pairsFound < n / 2) { while (counts[minVal] == 0) { minVal++; } while (counts[maxVal] == 0) { maxVal--; } double avg = (minVal + maxVal) / 2.0; averages.add(avg); counts[minVal]--; counts[maxVal]--; pairsFound++; } return averages.size(); }}Complexity
Time
O(N + K), where N is the length of `nums` and K is the range of values (101). Populating the `counts` array is `O(N)`. The two-pointer scan over the `counts` array takes `O(N/2 + K)` time because we form N/2 pairs and the pointers traverse the range K at most once. Thus, the total complexity is `O(N + K)`.
Space
O(N + K). We need `O(K)` space for the `counts` array and `O(N/2)` space for the `HashSet` in the worst case, where N is the number of elements and K is the range of values (101).
Trade-offs
Pros
The most efficient approach with linear time complexity.
Optimal for the given constraints on the range of numbers.
Cons
This approach is not general. It relies heavily on the small, non-negative integer range of the input values. It would be impractical if numbers were large or non-integers.
Solutions
Solution
class Solution {public int distinctAverages(int[] nums) { Arrays.sort(nums); Set<Integer> s = new HashSet<>(); int n = nums.length; for (int i = 0; i < n >> 1; ++i) { s.add(nums[i] + nums[n - i - 1]); } return s.size(); }}class Solution {public: int distinctAverages(vector<int> &nums) { sort(nums.begin(), nums.end()); unordered_set<int> s; int n = nums.size(); for (int i = 0; i < n >> 1; ++i) { s.insert(nums[i] + nums[n - i - 1]); } return s.size(); }};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)))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.