Abstract / Summary

Given a list of numbers, create a new list where each position holds the product of all other numbers except the one at that position.

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 69% (6+ million submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum

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 computes, for each element in an input vector, the product of all other elements. It does so by first scanning the input to gather global information, then constructing the output in a second pass. The algorithm deliberately treats the presence of zeros as a special condition, ensuring correct results without performing division by zero.

Key Steps

The first phase iterates over the input vector to count zeros and to accumulate the product of all non-zero values.

int64_t all = 1;
int zeros = 0;
for (auto n : nums)
    if (n == 0)
        zeros++;
    else
        all *= n;

After this loop, all holds the product of every non-zero element, while zeros records how many zeros appear in the original array.

The next segment determines the value that should be placed in the result when the current element is zero. If more than one zero exists, every position must be zero; if exactly one zero exists, the product of the non-zero elements is the only non-zero entry.

int allOneZero = all;
if (zeros > 1)
    allOneZero = 0;
if (zeros >= 1)
    all = 0;

Finally, the algorithm builds the output vector. For each element, it either inserts the pre-computed product for the single-zero case or divides the global product by the current element when the element is non-zero.

vector<int> result;
for (auto n : nums)
{
    if (n == 0)
        result.push_back(allOneZero);
    else
        result.push_back(all / n);
}

The function then returns the populated result vector.

Edge Cases Handled

When the input contains no zeros, zeros remains zero, all holds the product of all elements, and each output entry is simply all / n. The division is safe because n is never zero in this path.

If the input contains exactly one zero, the first loop still computes the product of all non-zero numbers. The conditional block sets all to zero, ensuring that division is never attempted for the zero element. The variable allOneZero retains the product of the non-zero elements, which is then placed at the position of the zero while all other positions receive zero.

When the input contains two or more zeros, the code forces allOneZero to zero, guaranteeing that every entry in the result vector is zero. This correctly reflects the mathematical fact that any product that excludes a particular element will still include at least one zero, yielding zero.

The use of a 64-bit accumulator (int64_t) mitigates overflow for typical integer ranges, allowing the intermediate product to exceed the 32-bit limit before the final values are cast back to int for the output vector.

Performance Optimizations

The algorithm performs only two linear traversals of the input vector, avoiding any nested loops or auxiliary data structures beyond the result container. By aggregating the product of non-zero elements in a single pass, it eliminates the need for separate prefix and suffix arrays that are common in alternative solutions.

The conditional logic that pre-computes allOneZero and possibly zeroes out all prevents unnecessary division operations for zero elements, reducing the computational cost in scenarios with many zeros.

Storing the intermediate product in a 64-bit variable reduces the frequency of overflow checks that would otherwise be required if the product were kept in a 32-bit type, thereby streamlining the arithmetic operations.

Overall, the implementation achieves the desired functionality with minimal passes, constant extra space, and careful handling of special cases to maintain correctness and efficiency.

Imagine you have a row of boxes, each holding a different number. This code is a clever helper that wants to create a new set of boxes for you. For every box in the row, the helper looks at all the other boxes and multiplies their numbers together to get a final total for that spot.

First, the helper looks through all the numbers. It keeps track of a big pile of multiplication and also counts how many zeros are hiding in the pile. Zeros are tricky because they make everything they touch turn into zero.

After counting the zeros, the helper prepares the answers. If there are no zeros at all, it just divides that big multiplication pile by the number in the current box to see what remains. If there is exactly one zero, that specific spot gets the multiplication total of all the other numbers, while every other spot gets a zero because they all still have that one pesky zero multiplying them. If there is more than one zero, everything results in a zero because no matter which box you look at, there will always be at least one zero left in the group to turn the total into nothing.

Once the helper finishes checking every box, it gathers all those totals into a new row and delivers it to you.

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

Time: linear
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	C#	Rust	JS			Go		PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	AdelDaniel										Dart
	aylei					Rust
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq		Python
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	pruthvikp		Python
	qiyuangong			Java
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02							C
	vthwang			Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
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