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 rules make it interesting:

• 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)

The naive intuition: for each index, loop over all the others and multiply.

from typing import List


class Solution:
    def productExceptSelf(self, 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 insight: everything-except-i factors cleanly into (product of nums[0..i-1]) × (product of nums[i+1..n-1]). Both families are classic prefix products (running products accumulated in one sweep, the multiplicative cousin of prefix sums) — one array built left-to-right, one right-to-left, then combine.

from typing import List


class Solution:
    def productExceptSelf(self, 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 insight: 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.

from typing import List


class Solution:
    def productExceptSelf(self, 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).