Abstract / Summary

Count pairs of points with the same distance between them.

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 58% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Math

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 method that counts the number of boomerang tuples that can be formed from a set of points on a 2-dimensional plane. A boomerang is an ordered triplet of distinct points (i, j, k) such that the distance from i to j equals the distance from i to k. The algorithm iterates over each point as a potential anchor, records the frequencies of squared distances to all other points, and then uses combinatorial counting to accumulate the total number of valid ordered pairs for each anchor.

Core Logic

The outer loop selects each point in turn to serve as the anchor of a potential boomerang. For each anchor, a dictionary maps squared distance values to the count of points that lie at that distance.

for i in range(len(points)):
    distances = defaultdict(int)
    x1, y1 = points[i]
    # inner processing follows

Inside the inner loop the algorithm skips the anchor itself, computes the squared Euclidean distance to every other point, and increments the corresponding counter.

for j in range(len(points)):
    if i == j:
        continue
    x2, y2 = points[j]
    squared = (x1 - x2)**2 + (y1 - y2)**2
    distances[squared] += 1

After all distances for the current anchor have been tallied, the method iterates over the frequency values. For each frequency d, the number of ordered pairs that can be formed is d * (d - 1), which directly adds to the running total.

for d in distances.values():
    result += d * (d - 1)

Finally, the accumulated result is returned.

return result

Distance Computation

The algorithm deliberately uses the squared distance rather than the true Euclidean distance. By avoiding the square-root operation, it eliminates floating-point arithmetic and potential precision issues while preserving the equality relationship required for boomerang detection. This choice also reduces computational overhead.

Counting Boomerangs

The expression d * (d - 1) derives from the number of ordered pairs that can be selected from d points sharing the same distance to the anchor. Since the order of the second and third points matters, the count is the permutation of two distinct points from the group, which is exactly d choices for the second point multiplied by d-1 choices for the third.

Edge Cases Handled

When the input list contains fewer than three points, the outer loop still executes, but the inner loop never finds a distinct second point, leaving the distance dictionary empty. Consequently, the inner aggregation over distances.values() contributes nothing, and the method correctly returns zero.

If multiple points share identical coordinates, the squared distance between the anchor and each coincident point becomes zero. The dictionary correctly aggregates these zero-distance occurrences, and the combinatorial formula still yields the appropriate number of ordered pairs, handling duplicate locations without special casing.

The continue statement ensures that a point is never paired with itself, guaranteeing that all counted boomerangs consist of three distinct indices.

Performance Optimizations

The use of a defaultdict(int) provides O(1) amortized insertion and update for distance frequencies, avoiding explicit existence checks. By resetting the dictionary for each anchor, the algorithm confines memory usage to the size of the current distance map rather than retaining a global structure.

Computing squared distances with integer arithmetic eliminates the cost of floating-point operations and avoids the overhead of calling a separate math function.

The nested loops iterate over the point list twice, but the inner loop skips the anchor early, reducing unnecessary work by one comparison per iteration. The final aggregation over the dictionary values processes only distinct distance values, which is typically far fewer than the total number of points, thereby minimizing the number of arithmetic operations required to update the result.

Imagine a big playground full of dots scattered all over the ground. Every dot has a special spot on a grid. This code acts like a tiny explorer that visits every single dot one by one to look for special shapes.

When the explorer stands on one dot, it looks at all the other dots in the playground. It uses a little bit of math to measure how far away every other dot is. It keeps a tally of these distances in a notebook. If it sees that two other dots are exactly the same distance away from the dot it is currently standing on, that forms a boomerang.

The explorer keeps a running total of these boomerang shapes. It checks every dot in the playground to see if any boomerangs can be made using that dot as the corner where the two arms meet. Once it has looked at every single dot and counted all the ways to pair them up by distance, it knows exactly how many boomerangs exist in the whole playground.

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

Time: polynomial
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	C++		Java			Python				TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java			Python		Go		TS
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	halfrost								Go
	JoshCrozier		JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007						Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM				C#
	varunu28			Java
	vli02									C
	wisdompeak	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

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