You are given a 0-indexed integer array nums of even length.
As long as nums is not empty, you must repetitively:
nums and remove it.nums and remove it.The average of two numbers a and b is (a + b) / 2.
2 and 3 is (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.length is even.0 <= nums[i] <= 100Problem 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.
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.
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.
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.
Time Complexity: O(n log n) for sorting, O(log n) for each search.
Space Complexity: O(1) for in-place 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 | 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 | — |
| 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 |
Leetcode | 2465. Number of Distinct Averages | Easy | Java Solution • Developer Docs • 800 views views
Watch 9 more video solutions →Practice Number of Distinct Averages with our built-in code editor and test cases.
Practice on FleetCode