2465. Number of Distinct Averages
Problem Description
The given problem involves an array of integers nums
, which has an even number of elements. We are instructed to perform a series of operations until the array becomes empty. In each operation, we must remove the smallest and the largest numbers from the array then calculate their average. This process is repeated until no numbers are left in the array. Our goal is to determine how many distinct averages we can get from these operations. It is important to note that in case of multiple instances of the minimum or maximum values, any occurrence of them can be removed.
Intuition
Considering that we need to find the minimum and maximum values of the array to calculate averages, a straightforward approach would be to sort the array first. With the array sorted, the minimum value will always be at the beginning of the array, and the maximum value will be at the end.
By sorting the array, we simplify the problem as follows:
- The minimum number of the array will be
nums[0]
, the second smallestnums[1]
, and so on. - The maximum number will be
nums[-1]
, the second-largestnums[-2]
, and similar for the other elements.
After each operation of removing the smallest and largest elements, the subsequent smallest and largest elements become the adjacent values (the next elements in the sorted array). Therefore, we avoid the need for repeated searching for min and max in an unsorted array.
To find the distinct averages:
- We iterate over half of the list (
len(nums) >> 1
), since every operation removes two elements. - For each iteration, we calculate the average of
nums[i]
andnums[-i - 1]
, which is effectively the average of the ith smallest and ith largest value in the array. - We use a
set
to collect these averages, which automatically ensures that only distinct values are kept. - The length of this set is the number of distinct averages we have calculated, which is what we want to return.
This algorithm is efficient because it sorts the array once, and then simply iterates through half of the array, resulting in a complexity of O(n log n) due to the sorting step.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The solution uses Python's built-in sorting mechanism to organize the elements in nums
from the smallest to the largest. By sorting the array, the algorithm simplifies the process of finding the smallest and largest elements in each step.
Here's a step-by-step explanation of the solution:
-
First,
nums.sort()
is called to sort the array in place. After the sort,nums[0]
will contain the smallest value, andnums[-1]
will contain the largest value, and so on for the ith smallest and ith largest elements. -
The generator expression
(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1))
then iterates through the first half of the elements in the sorted list. The expressionlen(nums) >> 1
is an efficient way to divide the length ofnums
by 2, using a bit-shift to the right. -
In each iteration,
nums[i] + nums[-i - 1]
calculates the sum of the ith smallest and ith largest element, which is equivalent to finding the sum of the elements at the symmetric positions from the start and the end of the sorted array. -
This sum is divided by 2 to calculate the average, but since the division by 2 is redundant when only interested in uniqueness (it does not affect whether the values are unique), it is not performed explicitly.
-
All of these sums (representing the averages) are then collected into a
set
. As sets only store distinct values, any duplicate averages calculated during the iteration will only appear once. -
Finally,
len(set(...))
returns the number of distinct elements in the set, which corresponds to the number of distinct averages that were calculated.
In terms of data structures and patterns used:
- An array/list data structure is the primary structure utilized.
- Sorting is the main algorithmic pattern applied.
- A set is used to deduplicate values and count distinct elements.
This solution is particularly elegant because it leverages the sorted order of the array and the property of set collections to avoid unnecessary computations and simplify logic.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach described above.
Suppose we have the following array:
1nums = [1, 3, 2, 6, 4, 5]
The problem requires us to continually remove the smallest and largest numbers, calculate their average, and determine the number of distinct averages we can get from these operations. Let's walk through this step by step:
Step 1: Sort the array. Sorting the array in increasing order will give us:
1nums.sort() # After sorting: [1, 2, 3, 4, 5, 6]
Step 2: Initialize an empty set to store unique averages.
1averages = set()
Step 3: Remove the smallest and largest numbers and calculate their averages.
1# Since there are six elements, we iterate over half of that, which is three elements.
2length_half = len(nums) >> 1 # Equivalent to dividing the length of nums by 2
3
4for i in range(length_half):
5 minimum = nums[i] # ith smallest after sorting
6 maximum = nums[-i - 1] # ith largest after sorting
7 # We calculate the sum since the division by 2 won't affect uniqueness
8 avg = minimum + maximum
9 averages.add(avg) # Add the sum (representing the average) to the set of unique averages
Iteration example:
- First iteration for
i=0
: minimum isnums[0]
which is1
; maximum isnums[-1]
which is6
. Their sum is1 + 6 = 7
. Add7
to the set of averages. - Second iteration for
i=1
: minimum isnums[1]
which is2
; maximum isnums[-2]
which is5
. Their sum is2 + 5 = 7
. As7
is already present in the set, it's not added again. - Third iteration for
i=2
: minimum isnums[2]
which is3
; maximum isnums[-3]
which is4
. Their sum is3 + 4 = 7
. Again, already present.
Step 4: The set of averages now has distinct sums. After the iterations, our set of averages will be:
1averages = {7}
Step 5: Get the number of unique averages.
Finally, we get the unique count by measuring the length of the set averages
:
1unique_averages_count = len(averages) # This will be 1
Based on this example, even though we calculated the average (its sum representation) three times, our set contains only one element. Therefore, the number of distinct averages in the nums
array we started with is 1
.
This example illustrates that the solution approach is efficient and avoids unnecessary complexity by using sorting, taking advantage of the properties of the set, and simplifying the problem into one that can be solved in linear time after sorting.
Solution Implementation
1from typing import List
2
3class Solution:
4 def distinct_averages(self, nums: List[int]) -> int:
5 # Sort the input list of numbers
6 nums.sort()
7
8 # Initialize an empty set to store unique averages
9 unique_averages = set()
10
11 # Calculate the average of each pair of numbers, one from the start
12 # and one from the end of the list, moving towards the middle
13 for i in range(len(nums) // 2): # Integer division to get half-way index
14 # Calculate the sum of the pair and add it to the set.
15 # We don't actually divide by 2 since it's the average of two nums and
16 # we are interested in distinct averages. The div by 2 won't affect uniqueness.
17 average = nums[i] + nums[-i - 1]
18
19 # Add the calculated sum (which represents an average) to the set
20 unique_averages.add(average)
21
22 # Return the number of unique averages
23 return len(unique_averages)
24
1class Solution {
2 public int distinctAverages(int[] nums) {
3 // Sort the array to facilitate pairing of elements
4 Arrays.sort(nums);
5
6 // Create an array to count distinct averages.
7 // Since the problem constraints are not given, assuming 201 is the maximum value based on the given code.
8 int[] count = new int[201];
9
10 // Get the length of the nums array
11 int n = nums.length;
12
13 // Initialize the variable to store the number of distinct averages
14 int distinctCount = 0;
15
16 // Loop through the first half of the sorted array
17 for (int i = 0; i < n / 2; ++i) {
18 // Calculate the average of the ith and its complement element (nums[i] + nums[n - i - 1])
19 // and increase the count for this average.
20 // We do not actually compute the average to avoid floating point arithmetic
21 // since the problem seems to be working with integer addition only.
22 int sum = nums[i] + nums[n - i - 1];
23 if (++count[sum] == 1) {
24 // If the count of a particular sum is 1, it means it is distinct, increase the distinctCount
25 ++distinctCount;
26 }
27 }
28
29 // Return the total count of distinct averages found
30 return distinctCount;
31 }
32}
33
1#include <algorithm> // For std::sort
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 int distinctAverages(vector<int>& nums) {
8 // Sort the input vector in non-decreasing order.
9 sort(nums.begin(), nums.end());
10
11 // Initialize a count array of size 201 to store
12 // the frequency of the sum of pairs.
13 int countArray[201] = {};
14
15 // Obtain the size of the input vector.
16 int numElements = nums.size();
17
18 // Initialize a variable to store the count of distinct averages.
19 int distinctCount = 0;
20
21 // Loop through the first half of the vector as we are creating pairs
22 // that consist of one element from the first half and one from the second.
23 for (int i = 0; i < numElements / 2; ++i) {
24 // Calculate the sum of the current pair: the i-th element and its corresponding
25 // element in the second half of the array (mirror position regarding the center).
26 int pairSum = nums[i] + nums[numElements - i - 1];
27
28 // If this sum appears for the first time, increase the distinct count.
29 if (++countArray[pairSum] == 1) {
30 ++distinctCount;
31 }
32 }
33
34 // Return the count of distinct averages.
35 return distinctCount;
36 }
37};
38
1// This function calculates the number of distinct averages that can be formed
2// by the sum of pairs taken from the start and end of a sorted array.
3function distinctAverages(nums: number[]): number {
4 // Sort the array in non-decreasing order
5 nums.sort((a, b) => a - b);
6
7 // Initialize a frequency array to keep track of the distinct sums
8 const frequency: number[] = Array(201).fill(0);
9
10 // Variable to hold the number of distinct averages
11 let distinctCount = 0;
12
13 // Determine the length of 'nums' array
14 const length = nums.length;
15
16 // Iterate over the first half of the sorted array
17 for (let i = 0; i < length >> 1; ++i) {
18 // Calculate the sum of the current element and its corresponding element from the end
19 const sum = nums[i] + nums[length - i - 1];
20
21 // Increase the frequency count for the calculated sum
22 frequency[sum]++;
23
24 // If this is the first time the sum appears, increment the distinctCount
25 if (frequency[sum] === 1) {
26 distinctCount++;
27 }
28 }
29
30 // Return the total number of distinct averages
31 return distinctCount;
32}
33
Time and Space Complexity
The time complexity of the code above is O(n log n)
and the space complexity is O(n)
.
Time Complexity
-
nums.sort()
: Sorting the list ofn
numbers has a time complexity ofO(n log n)
. -
The list comprehension
set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1))
iterates over the sorted list but only up to the halfway point, which isn // 2
iterations. Although the iteration is linear in time with respect to the number of elements it processes, the dominant term for time complexity comes from the sorting step.
Therefore, combining both steps we get O(n log n)
, which is the overall time complexity.
Space Complexity
-
The sorted in-place method
nums.sort()
does not use additional space other than a few variables for the sorting algorithm itself (O(1)
space). -
The list comprehension inside the
set
function creates a new list with potentiallyn / 2
elements (in the worst-case scenario, where all elements are distinct before combining them), and then aset
is created from this list. The space required for this set is proportional to the number of distinct sums, which is also up ton / 2
. Hence, this gives us a space complexity ofO(n)
.
Combining both considerations, the overall space complexity is O(n)
. This accounts for the space needed to store the unique sums in the worst-case scenario where all sums are distinct.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we