Abstract / Summary

Find how many different average values can be made by picking some numbers from a given list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sorting
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method distinctAverages that receives a list of integers and returns the count of unique average values that can be formed by pairing the smallest and largest remaining elements repeatedly. The algorithm first orders the input, then uses a two-pointer technique to traverse the sorted list from both ends, accumulating the sum of each pair in a set. Because the average of two numbers is proportional to their sum, the code stores the sums directly, avoiding a division operation. Finally, the size of the set, representing the number of distinct averages, is returned.

Key Steps

Sorting the Input

nums.sort()

Sorting arranges the numbers in non-decreasing order, which is essential for the two-pointer pairing strategy. After this step, the smallest element resides at index 0 and the largest at the last index.

Initializing the Data Structures

avgs  = set()
left  = 0
right = len(nums) - 1

A set named avgs is created to hold the unique sums of each pair. Two integer variables, left and right, are positioned at the start and end of the sorted list, respectively. These pointers will move toward each other as pairs are processed.

Pairing Elements and Recording Sums

while left <= right:
    avgs.add(nums[left] + nums[right])  # no need to divide by 2
    left  += 1
    right -= 1

The loop continues while the left pointer has not crossed the right pointer. In each iteration, the elements at the current left and right positions are summed and added to the avgs set. The comment notes that dividing by two is unnecessary because distinctness of averages is preserved by the sums. After recording the sum, left advances forward and right retreats backward, preparing the next outermost pair.

Returning the Result

return len(avgs)

The method concludes by returning the cardinality of the avgs set, which corresponds to the number of distinct average values that can be formed from the described pairing process.

Edge Cases Handled

When the input list contains a single element, the sorting step leaves the list unchanged, and the pointers both start at index 0. The loop condition left <= right holds true for the first iteration, causing the element to be paired with itself. The sum (twice the element) is added to the set, and the pointers move past each other, terminating the loop. Consequently, the method correctly returns 1, reflecting the single possible average.

If the list is empty, the length is zero, making right equal to -1. The loop condition fails immediately because left (0) is not less than or equal to right (-1). No sums are added to the set, and the method returns 0, indicating that no averages can be formed.

When the list contains duplicate values, the sorting step groups identical numbers together, but the two-pointer approach still pairs the outermost elements regardless of duplication. Because the set automatically discards duplicate sums, the final count reflects only unique averages, even if many pairs produce the same sum.

Performance Optimizations

The algorithm leverages in-place sorting, which avoids allocating additional memory for a sorted copy of the input. The two-pointer traversal processes each element exactly once, resulting in a linear pass after sorting. By storing sums instead of actual averages, the code eliminates a division operation inside the loop, reducing computational overhead. The use of a hash set for avgs provides constant-time insertion and membership checks, ensuring that duplicate sums are filtered efficiently without extra scanning. Overall, the combination of in-place sorting, a single linear scan, and hash-based deduplication yields a solution that scales well with the size of the input list.

Imagine a row of number cards lined up on the floor. First, the cards get sorted so the smallest numbers are on the far left and the biggest numbers are on the far right. Think of the left pointer as a tiny robot at the beginning of the line and the right pointer as another tiny robot at the very end.

These two robots walk toward each other. Every time they meet at their current spots, they pick up the number card they are standing on and add those two numbers together. They drop these sums into a special collection box. This box is magical because it only keeps one copy of each unique sum, even if a sum happens again later. The left robot moves one step forward and the right robot moves one step backward, and they keep grabbing cards and finding sums until they meet in the middle and have no more cards left to pick up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java		C++		Python		TS
	WalkCCC	Java		C++		Python
	leetcode.ca	Java		C++	Go	Python	Rust	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality