How do you solve Product of Array Except Self without division?

answer[i] is the product of everything left of i times everything right of i. A left-to-right pass writes the running prefix product into answer[i]; a right-to-left pass multiplies each answer[i] by the running suffix product.

Why not multiply everything and divide by nums[i]?

The problem forbids division, and division also breaks on zeros: with one zero, every product except at the zero's index is 0, and dividing by zero is undefined. Prefix and suffix products handle zeros with no special cases.

What is the space complexity?

O(1) extra space besides the output array, because the prefix products are stored in the answer array itself and the suffix product is a single running variable. A version with separate prefix and suffix arrays uses O(n).

Product of Array Except Self

Return the product of every element except the current one, without division, using prefix and suffix products.

MediumSolve on LeetCode

Problem Understanding

Product of Array Except Self: given an integer array nums, return answer where answer[i] is the product of every element of nums except nums[i]. It must run in O(n) time without using division.

Example: [1, 2, 3, 4] returns [24, 12, 8, 6].

Attempt 1: Multiply Everything Else

For each index, multiply all the other elements: O(n²) time. Multiplying everything once and dividing by nums[i] would be O(n), but division is not allowed — and it fails on zeros anyway. The trick is to notice what answer[i] is made of.

The Intuition: Left Product × Right Product

Everything except nums[i] is everything left of i and everything right of i:

answer[i] = (nums[0] × … × nums[i−1]) × (nums[i+1] × … × nums[n−1])

Both halves are running products — the multiplicative version of a prefix sum:

Left pass: keep prefix = 1; at each i, write answer[i] = prefix, then prefix *= nums[i].
Right pass: keep suffix = 1; walking back, answer[i] *= suffix, then suffix *= nums[i].

The prefix products live in the output array itself, so the only extra memory is one variable per pass.

Interactive Walkthrough

answer[i] = (PRODUCT LEFT OF i) × (PRODUCT RIGHT OF i)

PREFIX = 1

nums

answer

prefix

suffix

—

prefix = 1: the product of nothing. answer[i] will first hold the product of everything left of i

answer[0] = prefix = 1 (everything left of 0). Then prefix × nums[0] = 1 × 1 = 1

Array

nums is on top and answer underneath. In the left pass the elements already folded into prefix are marked as each answer[i] is written; in the right pass the marking comes back from the other end as suffix grows and each answer[i] is completed.

Dry Run Table

Input: [1, 2, 3, 4]

Pass	`i`	Running product before	`answer` after
left	0	prefix 1	`[1, ·, ·, ·]`
left	1	prefix 1	`[1, 1, ·, ·]`
left	2	prefix 2	`[1, 1, 2, ·]`
left	3	prefix 6	`[1, 1, 2, 6]`
right	3	suffix 1	`[1, 1, 2, 6]`
right	2	suffix 4	`[1, 1, 8, 6]`
right	1	suffix 12	`[1, 12, 8, 6]`
right	0	suffix 24	`[24, 12, 8, 6]`

The Solution Template

Prefix products in the output array, then a running suffix product.

Product of Array Except Self Code

1var productExceptSelf = function(nums) {
2    const n = nums.length;
3    const answer = new Array(n).fill(1);
4    let prefix = 1;
5    for (let i = 0; i < n; i++) {
6        answer[i] = prefix;
7        prefix *= nums[i];
8    }
9    let suffix = 1;
10    for (let i = n - 1; i >= 0; i--) {
11        answer[i] *= suffix;
12        suffix *= nums[i];
13    }
14    return answer;
15};

Edge Cases & Common Mistakes

One zero ([-1, 1, 0, -3, 3]): only the zero's own index gets a non-zero product — [0, 0, 9, 0, 0].
Two or more zeros: every product includes a zero — all 0.
Negative numbers: signs multiply through with no special handling.
Using division: not allowed, and undefined when an element is zero.
Writing before reading in the left pass: set answer[i] = prefix before multiplying nums[i] into prefix, or answer[i] would include nums[i] itself.

Summary

answer[i] is the product to its left times the product to its right. Two passes of running products — the multiplicative form of prefix sums — give O(n) time and O(1) extra space without division.

Count Vowels in Ranges

Subarray Sum Equals K