Abstract / Summary

Count the number of integer triplets whose squares add up to a given target value.

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

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 ordered triples ((a, b, c)) of positive integers not exceeding a given limit n such that the sum of the squares of a and b equals the square of c. The algorithm builds a collection of all square values up to n, then examines every possible pair of squares to see whether their sum also appears in the collection. Each successful match increments a counter, which is finally returned.

Key Steps

Precomputing Squares

The first significant operation creates a set containing the squares of all integers from 1 through n. Using a set enables constant-time membership checks later in the algorithm.

squares = set([ i*i for i in range(1, n + 1) ])

Nested Iteration and Membership Test

The core logic iterates over every element a in the set of squares, and for each a iterates over every element b. For each pair, the code checks whether the sum a + b is itself a member of the precomputed set. When the condition holds, the result counter is increased.

for a in squares:
    for b in squares:
        if a + b in squares:
            result += 1

Returning the Count

After all pairs have been examined, the accumulated count is returned as the final answer.

return result

Edge Cases Handled

When n is zero or negative, the range used to generate squares yields an empty sequence, resulting in an empty squares set. The subsequent loops have no iterations, and the method correctly returns zero, representing the absence of any valid triples.

For the smallest positive input (n = 1), the set contains only the value 1. The nested loops evaluate the single pair (1, 1), but the sum 2 is not present in the set, so the counter remains zero. This demonstrates that the method gracefully handles inputs where no triples exist.

If n is a large integer, the set construction still succeeds because it relies on a straightforward comprehension that scales with the number of integers up to n. The algorithm does not assume any particular ordering or distribution of squares, making it robust across the full range of permissible inputs.

Performance Optimizations

The most notable optimization is the use of a hash-based set for storing square values. This choice provides average-case constant-time lookups for the expression a + b in squares, eliminating the need for linear scans or binary searches.

Precomputing the squares once, rather than recomputing i*i inside the nested loops, reduces redundant arithmetic operations. The comprehension that builds the set executes in a single pass, ensuring that each square is calculated exactly once.

Iterating directly over the set of squares avoids the overhead of index-based loops and leverages Python’s efficient iterator protocol. The nested structure, while exhaustive, benefits from the fast membership test, allowing the algorithm to focus on the combinatorial aspect without incurring additional search costs.

Imagine a giant toy box filled with square tiles. Each tile has a special number on it, like one, four, nine, and so on. These numbers are made by multiplying a number by itself, just like how two times two makes four.

The code starts by making a collection of all these square tiles up to a certain size. Think of this like gathering all the square blocks you have in your box and putting them on a table in front of you.

Next, the code goes on a little treasure hunt. It picks up one square tile and adds it to another square tile from the table. It checks carefully to see if the new total is also a square tile that belongs in the set. If the two tiles fit together perfectly to make a third square tile, then a secret counter goes up by one.

This process keeps happening over and over, testing every possible pair of tiles from the table. Every time a perfect match is found, the counter grows. By the time every single pair has been checked, the counter shows exactly how many of these groups of three square tiles were found hiding in the collection.

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
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim							C
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	suxrobGM						C#
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	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