Number of Distinct Averages - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an even-length integer array. In each step, remove the smallest and largest numbers, compute their average, and store it. Repeat until the array is empty. The goal is to return how many distinct averages appear during this process.
Approach 1: Using Hash Maps / Hash Set (O(n log n) time, O(n) space)
This approach focuses on tracking unique averages using a hash-based structure. First, sort the array so the smallest and largest values can be accessed easily. Then iterate using two pointers: one at the beginning and one at the end of the array. For every pair, compute the average using (nums[left] + nums[right]) / 2 and insert the result into a hash set. Because sets store only unique values, duplicates are automatically removed. Continue moving the pointers inward until all elements are processed.
The key idea is that the order of removal does not affect the result once the array is sorted. Every step always combines the smallest and largest remaining elements. The hash structure guarantees O(1) average insertion and lookup, so counting distinct averages becomes straightforward. This method works well for general hash table problems where uniqueness needs to be tracked efficiently.
Approach 2: Using Sorting and Two Pointers (O(n log n) time, O(n) space)
Another clean solution relies on sorting and the classic two-pointer technique. After sorting the array, place one pointer at the start and another at the end. Each iteration forms a pair consisting of the minimum and maximum remaining values. Compute their sum or average and store it in a set. Move the left pointer forward and the right pointer backward until they cross.
The sorting step dominates the runtime with O(n log n), while the pairing process itself runs in O(n). This approach highlights a common pattern in two pointers and sorting problems: sort first, then process symmetric elements from both ends. It avoids repeated scanning for minimum or maximum values and keeps the implementation compact.
Recommended for interviews: Interviewers usually expect the sorting + two-pointer solution. It demonstrates recognition of a symmetric pairing pattern and efficient iteration across the array. Mentioning a hash set to track unique averages shows awareness of constant-time lookups. A brute-force idea (repeatedly scanning for min and max) shows baseline understanding, but the sorted two-pointer solution shows stronger algorithmic thinking.
Approach 1: Approach 1: Using Hash Maps
This approach utilizes hash maps (or dictionaries) to store and efficiently query required data. The hash map data structure offers average constant time complexity for insertions and lookups, making it ideal for problems where we need to frequently access or update information.
This C solution implements a simplistic hash table using separate chaining to handle collisions. We define an entry structure that holds a key-value pair and we use an array of entry pointers as our hash table. The 'hashFunction' maps the key to an array index, and 'insert' adds new entries, while 'search' retrieves the value for a given key, or -1 if the key isn't found.
Complexity
Time Complexity: O(1) on average for insert and search, O(n) in the worst case due to collisions.
Space Complexity: O(n), where n is the number of elements stored in the hash table.
Approach 2: Approach 2: Using Sorting and Binary Search
This approach involves first sorting the data, which allows us to use binary search for efficient lookups. Although this incurs a sorting overhead, it can be effective when dealing with static data where many lookups are needed and few or no updates.
This C solution demonstrates sorting an array using qsort and then performs a binary search. We define a comparison function to allow qsort to order the array. The binarySearch function uses iteration to efficiently find an element, returning its index or -1 if absent.
Complexity
Time Complexity: O(n log n) for sorting, O(log n) for each search.
Space Complexity: O(1) for in-place sorting.
Approach 3: 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.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Approach 4: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Maps | Time Complexity: O(1) on average for insert and search, O(n) in the worst case due to collisions. |
| Approach 2: Using Sorting and Binary Search | Time Complexity: O(n log n) for sorting, O(log n) for each search. |
| Sorting | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set with Pair Tracking | O(n log n) | O(n) | General solution when you need to track distinct averages efficiently |
| Sorting + Two Pointers | O(n log n) | O(n) | Preferred interview approach when pairing smallest and largest elements |
Video Solution
Leetcode | 2465. Number of Distinct Averages | Easy | Java Solution • Developer Docs • 905 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Distinct Averages easy or hard?
How to solve Number of Distinct Averages in O(n)?
What is the best approach for Number of Distinct Averages?
What data structure is used in Number of Distinct Averages?
What is the time complexity of Number of Distinct Averages?
Number of Distinct Averages Python or Java solution approach?
Is Number of Distinct Averages asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Number of Distinct Averages with our built-in code editor and test cases.
Practice on FleetCode