Product of Array Except Self Solution

Problem

Given an array of integers, construct a new array where each position holds the product of every other element — every element except the one at that index. The solution must run in O(n) time and cannot use division.

Example:

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: output[1] = 1 × 3 × 4 = 12 — every element multiplied together except nums[1].

A counter-example that illustrates why division fails: for nums = [0, 1, 2], the total product is 0, so you can't divide by any element — yet the correct answer [2, 0, 0] is well-defined. The prefix/suffix approach produces it automatically.

Intuition

For any index, the answer is the product of everything to its left times the product of everything to its right. These two halves can be computed in two linear passes: a forward pass that accumulates a running left product into the output array, then a backward pass that folds in a running right product. No intermediate arrays are needed — just one scalar variable on the second pass.

Approach 1 — Brute Force

For each position, scan the entire array and multiply every element except the one at that index.

Steps:

Allocate an output array of the same length, initialized to 1.
For each index i, iterate over all indices j.
Skip when j == i; multiply output[i] by nums[j] for every other j.
Return output.

1def productExceptSelf(nums: list[int]) -> list[int]:
2    n = len(nums)
3    output = [1] * n
4
5    for i in range(n):
6        for j in range(n):
7            if i != j:
8                output[i] *= nums[j]
9
10    return output

Time: O(n²) — two nested loops, each iterating up to n times.
Space: O(1) — no extra storage beyond the required output array.

Approach 2 — Prefix & Suffix Products

Exploit the fact that output[i] = (product of nums[0..i-1]) × (product of nums[i+1..n-1]). Compute the left half in a single forward pass into the output array, then fold in the right half with a running variable on a backward pass.

Steps:

Allocate the output array and set output[0] = 1 — the empty left product for the first position.
Walk left to right: output[i] = output[i-1] * nums[i-1], so each slot holds the product of everything to its left.
Initialize right_product = 1 — the empty right product for the last position.
Walk right to left: multiply output[i] *= right_product, then update right_product *= nums[i] to extend the suffix one step leftward.
Return output.

Trace on [1, 2, 3, 4]:

After forward pass: output = [1, 1, 2, 6]
Backward (right_product starts at 1): i=3 → 6×1=6, rp→4 | i=2 → 2×4=8, rp→12 | i=1 → 1×12=12, rp→24 | i=0 → 1×24=24
Result: [24, 12, 8, 6] ✓

1def productExceptSelf(nums: list[int]) -> list[int]:
2    n = len(nums)
3    output = [1] * n
4
5    # output[i] = product of all elements to the left of index i
6    for i in range(1, n):
7        output[i] = output[i - 1] * nums[i - 1]
8
9    # Multiply in the suffix product while sweeping from right to left
10    right_product = 1
11    for i in range(n - 1, -1, -1):
12        output[i] *= right_product
13        right_product *= nums[i]  # extend the suffix one position to the left
14
15    return output

Time: O(n) — two independent linear passes over the array.
Space: O(1) — one right_product scalar; the output array is required by the problem and not counted as extra space.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only to establish a baseline in an interview before optimizing
Prefix & Suffix Products	O(n)	O(1)	Always — handles zeros naturally, requires no division

Common Mistakes

Off-by-one in the forward pass: output[i] must hold the product of nums[0..i-1], not nums[0..i]. Start the forward loop at index 1 and initialize output[0] = 1, not nums[0] — the element at index 0 has nothing to its left.
Initializing right_product to nums[n-1] instead of 1: This double-counts the last element for output[n-1]. The suffix variable represents elements already swept past, which is empty at the start, so it must begin at 1 and be updated after each position is finalized.
Reaching for division: Division breaks when any element is zero — you'd get a zero total product and a divide-by-zero (or wrong result) at that position. The prefix/suffix approach produces the correct answer for all zero configurations with no special handling.
Allocating two separate O(n) prefix and suffix arrays: The natural first step is to build both arrays explicitly, then combine them. This works but wastes space — the suffix can be folded directly into the output array using just one running variable on the backward pass.
Adding a special case for zeros: A common detour is to count zeros and branch separately for "one zero" vs "two or more zeros." This is unnecessary; the two-pass algorithm already handles every configuration correctly, including arrays with multiple zeros.

Product of Array Except Self — Solution