Product of Array Except Self

Problem

Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].

Two constraints:

• You may not use division.
• The algorithm must run in O(n) time.

Follow-up: compute it with O(1) extra space, not counting the output array.

All prefix/suffix products are guaranteed to fit in a 32-bit integer.

Examples

Example 1: nums = [1, 2, 3, 4] → [24, 12, 8, 6] For index 0: 2·3·4 = 24; for index 1: 1·3·4 = 12; and so on.

Example 2: nums = [-1, 1, 0, -3, 3] → [0, 0, 9, 0, 0] Every position except the zero’s own picks up the 0 factor; at the zero’s index the remaining product is (-1)·1·(-3)·3 = 9.

Constraints

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30

n up to 10^5 rules out the O(n²) pairwise product; the no-division rule rules out the “total product / nums[i]” shortcut (which zeros break anyway).

Think about it first

TL;DR

Prefix pass into the output + running suffix multiplier — O(n) time, O(1) extra space (output excluded).

Approach 1 — Brute force (pairwise products)

For each index, loop over all the other elements and multiply them.

from typing import List


def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Complexity: O(n²) time, O(1) extra space. At n = 10^5 that’s 10^10 multiplications — well past the budget.

Approach 2 — Prefix and suffix product arrays

The product of everything except i factors into (product of nums[0..i-1]) × (product of nums[i+1..n-1]). Both are prefix products: running products accumulated in one sweep. Build one array left-to-right and one right-to-left, then combine.

from typing import List


def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1] * n   # prefix[i] = product of nums[:i]
    suffix = [1] * n   # suffix[i] = product of nums[i+1:]

    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] * nums[i + 1]

    return [prefix[i] * suffix[i] for i in range(n)]

Walkthrough on Example 1, nums = [1, 2, 3, 4]:

1. prefix = [1, 1, 2, 6] (nothing before index 0; then 1; 1·2; 1·2·3).
2. suffix = [24, 12, 4, 1] (2·3·4 after index 0; 3·4; 4; nothing after the last).
3. Combine: [1·24, 1·12, 2·4, 6·1] = [24, 12, 8, 6].

Complexity: O(n) time, O(n) extra space for the two helper arrays.

Approach 3 — Two passes, O(1) extra space

The prefix array can be the output array, and the suffix products never need storing. A single scalar carried through a right-to-left sweep suffices, since each suffix value is used exactly once, immediately after it is computed.

from typing import List


def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    answer = [1] * n

    for i in range(1, n):                  # answer[i] = product of nums[:i]
        answer[i] = answer[i - 1] * nums[i - 1]

    suffix = 1                             # product of nums[i+1:]
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]

    return answer

Walkthrough on Example 1, nums = [1, 2, 3, 4]:

1. After the forward pass: answer = [1, 1, 2, 6] (prefix products).
2. Backward pass, suffix = 1:
   • i=3: answer[3] = 6·1 = 6; suffix ← 4.
   • i=2: answer[2] = 2·4 = 8; suffix ← 12.
   • i=1: answer[1] = 1·12 = 12; suffix ← 24.
   • i=0: answer[0] = 1·24 = 24.
3. answer = [24, 12, 8, 6].

Complexity: O(n) time, O(1) extra space (the output array doesn’t count per the problem statement).

Why not divide the total product by each element? Besides being explicitly banned, it breaks on zeros (division by zero, and with two zeros every answer is 0) — the prefix/suffix method handles zeros with no special cases, as Example 2 shows: any index other than the zero’s has the 0 folded into its prefix or suffix, while the zero’s own index sees only the other factors (9).

Common pitfalls

• Off-by-one in what prefix[i] means: it must exclude nums[i] (product of the strictly-before elements). Including it double-counts the element you’re supposed to skip.
• Sneaking division in and crashing (or zeroing everything) when the array contains one or two zeros.
• Updating suffix before multiplying it into answer[i] in the backward pass — that folds nums[i] into its own answer.
• Assuming products overflow: in Python they can’t, but state the 32-bit guarantee if asked in a C++/Java context.

Pattern takeaway

When each answer is an aggregate over “everything except me” (or any range), decompose it into a prefix aggregate and a suffix aggregate computed in one sweep each. And when a helper array is consumed in strict order right after being produced, collapse it into a running scalar — the standard route from O(n) extra space to O(1).