Abstract / Summary

Count sets of four different numbers from an array where the sum of two equals the product of the other two.

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 65% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Enumeration
• Hash Table

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 countQuadruplets that receives a list of integers and returns the number of quadruplets (a, b, c, d) satisfying a < b < c < d and nums[a] + nums[b] + nums[c] == nums[d]. The algorithm builds an auxiliary structure to locate occurrences of each value, then iterates over all ordered triples of indices and checks whether a matching fourth index exists.

Key Steps

Building the Position Map

The first phase creates a dictionary that maps each distinct number in the input list to a list of its positions. This enables constant-time lookup of all indices where a particular value appears.

lookup = defaultdict(list)
for i, n in enumerate(nums):
    lookup[n].append(i)

By storing every index rather than a single occurrence, the method can later verify the ordering constraint d > c for each candidate fourth index.

Enumerating Triples

The core of the algorithm consists of three nested loops that generate every ordered triple (a, b, c) with strictly increasing indices. The outermost loop selects a, the middle loop selects b starting from a + 1, and the innermost loop selects c starting from b + 1. For each triple the sum of the three corresponding values is computed.

for a in range(size):
    for b in range(a + 1, size):
        for c in range(b + 1, size):
            total = nums[a] + nums[b] + nums[c]

Validating the Fourth Index

After the sum total is obtained, the code checks whether this sum appears as a key in the previously built lookup dictionary. If it does, the method iterates over the stored positions for that sum and increments the result counter for each position l that satisfies l > c, thereby enforcing the required ordering d > c.

if total in lookup:
    for l in lookup[total]:
        if l > c:
            result += 1

The final value of result is returned as the answer.

Edge Cases Handled

When the input list is empty or contains fewer than four elements, the outer loops never produce a valid triple, and the method returns zero without performing any further work. Duplicate values are naturally accommodated because the lookup dictionary stores all indices for each value; the inner check l > c ensures that each occurrence is considered independently while preserving the strict index ordering. The algorithm also correctly handles negative numbers and zero, as the sum calculation and dictionary lookup are agnostic to sign.

Performance Optimizations

The most notable optimization is the use of a precomputed position map (lookup). By converting the existence test for the fourth element into a dictionary membership check, the algorithm avoids scanning the entire list for each triple. This reduces the inner work from a linear scan to iterating only over the positions that actually contain the required sum. Moreover, the condition l > c filters out indices that would violate the ordering constraint, preventing unnecessary counting. The three-level nested loops are limited to generating ordered triples, which is the minimal enumeration required to respect the a < b < c ordering, and the early dictionary lookup prevents deeper nesting for triples that cannot possibly form a valid quadruplet.

Imagine a long train track made of many numbered blocks. The goal is to pick four of these blocks in order from left to right. When you add the numbers on the first three blocks, the total must be the same as the number written on the fourth block.

First, the code builds a little map or a notebook where it writes down every spot where each number is hiding on the track. This makes it super fast to look up where a specific number is later.

Then, there are three loops that act like three friends moving along the track. The first friend picks a starting block, the second friend picks a block further down, and the third friend picks an even later block. The code adds the numbers from these three friends' blocks together to get a target sum.

The notebook is checked to see if a fourth block with that target number exists anywhere further down the track beyond the third friend. If that special block is found, it means a perfect group of four has been discovered. Every time this happens, a counter goes up by one to keep track of all the winning sets found along the way.

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