Prefix Product

Return an array where each element is the product of all the others — i.e. out[i] = product of nums except nums[i] — without using division.

productExceptSelf(nums)

Input format: space-separated integers. Output the result, space-separated.

Examples

[1, 2, 3, 4]    // → [24, 12, 8, 6]
[2, 3]          // → [3, 2]
[5]             // → [1]

Walkthrough

Thinking it through

The natural first instinct: multiply everything, then divide by nums[i]. That works arithmetically, but division is forbidden — and for good reason, since it breaks the moment any element is zero, and multiple zeros make it even messier.

So: how do you compute, for every position, the product of everything except that position, without dividing?

Breaking the problem into two halves

"Everything except position i" is two independent pieces: everything strictly left of i, and everything strictly right. Knowing both products and multiplying them gives exactly what you want, without touching nums[i] itself.

That suggests two auxiliary arrays: a prefix-product array (product of everything before each index) and a suffix-product array (product of everything after). The answer at i is prefix[i] times suffix[i].

Collapsing two arrays into one pass with O(1) extra space

Build the output in two sweeps over the same array:

Left to right, keep a running product (starting at 1). Before folding in nums[i], write the running product into out[i] — that's everything strictly left of i. Then multiply the running product by nums[i].
Right to left, same idea, but multiply (not overwrite) out[i] by a running product of everything to the right.

After both passes, out[i] holds prefix times suffix — exactly the product of everything except nums[i].

Why this works even with zeros

No division means zeros are handled gracefully. One zero element makes every other position's answer zero (the zero sits in their prefix or suffix product), while the zero's own position ends up as the product of the non-zero elements — computed correctly with no special-casing.

Why this beats the brute force

The naive approach — loop through the array skipping one index, for every index — is O(n²), redoing an O(n) scan n times. The prefix/suffix technique carries forward running products instead of recomputing them — two linear sweeps, O(n) total, only the output array as extra memory. "Running total from the left, running total from the right" applies to any "everything except this position" problem.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.