LeetCode 2465 - Number of Distinct Averages

LeetCode Problem 2465

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Sorting

Solution

Problem Understanding

The problem requires calculating the number of distinct averages generated from a sequence of numbers using a specific process. The input is an integer array nums of even length. The process repeatedly removes the smallest and largest numbers from the array, calculates their average, and continues until the array is empty. The output is the number of unique averages obtained through this process.

The constraints tell us that the array is relatively small (up to 100 elements), which makes even a straightforward approach feasible, but we should still aim for clarity and efficiency. The array always has an even number of elements, ensuring that every minimum has a corresponding maximum to pair with. Input numbers range from 0 to 100, which simplifies handling and allows safe use of floating point division without worrying about extreme values.

Important edge cases include arrays where all numbers are equal, arrays with repeated numbers, and arrays with only two elements. These cases could produce only one unique average or multiple repeated averages, and the implementation must correctly count only distinct values.

Approaches

The brute-force approach is to simulate the process exactly as described. At each step, we search for the minimum and maximum values, remove them, compute their average, and store it in a set to count distinct averages. This method is correct but not optimal because repeatedly searching for min and max values in an unsorted array is inefficient, with a time complexity of O(n²) in the worst case.

The key observation for optimization is that we can first sort the array. Once sorted, the smallest number is always at the start, and the largest is always at the end. We can then pair elements from the two ends using two pointers, calculate their averages, and insert them into a set. Sorting takes O(n log n) time, and the two-pointer pass takes O(n) time, leading to an overall efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches for min and max, stores averages in a set
Optimal	O(n log n)	O(n)	Sorts the array once, uses two pointers to compute averages

Algorithm Walkthrough

1. Sort the input array nums in ascending order. Sorting ensures the minimum is at the start and the maximum is at the end.

2. Initialize two pointers: left at the start (0) and right at the end (len(nums) - 1).

3. Initialize an empty set averages to store unique averages.

4. While left < right:

5. Calculate the average of nums[left] and nums[right].

6. Add this average to the set averages.

7. Increment left and decrement right to move inward.

8. Once the loop ends, return the size of the averages set as the number of distinct averages.

Why it works: The algorithm works because pairing the smallest and largest elements in a sorted array mimics the removal process in the problem description. By using a set, duplicate averages are automatically ignored, guaranteeing that the final count represents distinct averages.

Python Solution

from typing import List

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        averages = set()
        while left < right:
            avg = (nums[left] + nums[right]) / 2
            averages.add(avg)
            left += 1
            right -= 1
        return len(averages)

This Python solution first sorts nums to make the smallest and largest elements easily accessible. It uses two pointers to traverse from both ends, calculating averages and storing them in a set. Using a set ensures that only unique averages are counted. Finally, it returns the number of distinct averages.

Go Solution

import "sort"

func distinctAverages(nums []int) int {
    sort.Ints(nums)
    left, right := 0, len(nums)-1
    averages := make(map[float64]struct{})
    for left < right {
        avg := float64(nums[left]+nums[right]) / 2
        averages[avg] = struct{}{}
        left++
        right--
    }
    return len(averages)
}

In Go, we sort the slice using sort.Ints. We then use two pointers, calculate the average as a float64, and store it in a map to ensure uniqueness. Go does not have a native set type, so a map with empty struct values is used. The logic mirrors the Python solution.

Worked Examples

Example 1: nums = [4,1,4,0,3,5]

Step	nums	left	right	avg	averages
Initial	[0,1,3,4,4,5]	0	5	2.5	{2.5}
1	[0,1,3,4,4,5]	1	4	2.5	{2.5}
2	[0,1,3,4,4,5]	2	3	3.5	{2.5, 3.5}

Return 2.

Example 2: nums = [1,100]

Step	nums	left	right	avg	averages
Initial	[1,100]	0	1	50.5	{50.5}

Return 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime; the two-pointer pass is O(n)
Space	O(n)	The set stores at most n/2 averages

The algorithm efficiently handles all inputs up to the constraints of length 100, and memory usage is minimal since the set stores only the distinct averages.

Test Cases

# Provided examples
assert Solution().distinctAverages([4,1,4,0,3,5]) == 2  # multiple averages with duplicates
assert Solution().distinctAverages([1,100]) == 1  # only one average

# Boundary and edge cases
assert Solution().distinctAverages([0,0]) == 1  # identical elements
assert Solution().distinctAverages([1,2,3,4]) == 2  # consecutive numbers
assert Solution().distinctAverages([5,5,5,5,5,5]) == 1  # all identical
assert Solution().distinctAverages([1,3,5,7,9,11]) == 3  # evenly spaced numbers
assert Solution().distinctAverages([0,1,2,99,100,50]) == 3  # mix of extremes and middle

Test	Why
[4,1,4,0,3,5]	Tests duplicates and multiple averages
[1,100]	Minimal case, single average
[0,0]	Identical numbers
[1,2,3,4]	Small array with consecutive numbers
[5,5,5,5,5,5]	All identical numbers
[1,3,5,7,9,11]	Sequence with consistent spacing
[0,1,2,99,100,50]	Mix of extremes and middle values

Edge Cases

One edge case is an array where all elements are identical. Here, every calculated average is the same, and the algorithm must correctly return 1. Sorting does not affect the outcome, and the set ensures duplicates are ignored.

A second edge case is an array of length 2. The algorithm handles this naturally since the left pointer starts at 0 and the right at 1, calculating a single average and returning 1.

A third edge case involves arrays with large gaps between numbers. For example, [0,50,100,200] produces distinct averages like 100 and 75. Sorting ensures correct pairing, and the set accurately counts only unique values, handling potential floating point averages correctly.