Product of Array Except Self

The tempting shortcut is to compute the total product once and divide it by nums[i] for each answer — but division is explicitly disallowed, and it would break on a zero anyway. The actual insight: answer[i] is the product of everything before i times everything after i. Those two pieces can each be built with a simple running pass.

Brute Force

Time O(n²)Space O(1)

For each index, multiply every other element.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = []
        for i in range(n):
            product = 1
            for j in range(n):
                if j != i:
                    product *= nums[j]
            result.append(product)
        return result

Correct, but for each of the n output positions it redoes an O(n) multiplication pass — O(n²) total, recomputing overlapping products from scratch every time.

Prefix × Suffix Products

OptimalTime O(n)Space O(1)

answer[i] is (product of nums[0..i-1]) * (product of nums[i+1..n-1]). Build the prefix products left-to-right directly into the answer array, then sweep right-to-left multiplying in the suffix products with a single running variable — no division, and no second array needed.

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        answer = [1] * n

        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

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

        return answer

Watch the answer array first fill with left products, then get multiplied by right products in a single right-to-left sweep:

prefix pass: left to rightprefix = 1suffix = 1

nums (top) / answer (bottom)

1 / 10

currentcomparingresult

Start: answer is all 1s and both running products are 1, the product of an empty side. The prefix pass will write the product of everything left of each index.

Correctness: after the prefix pass, answer[i] holds the product of everything strictly to the left of i. Multiplying in the suffix pass’s running product — everything strictly to the right of i — gives exactly the product of all elements except nums[i], with no division and no risk of dividing by a zero.

Complexity: two linear passes over the array — O(n) time. Only two scalar running variables (prefix, suffix) are used beyond the output array, which the problem explicitly excludes from the space count — O(1) extra space, answering the follow-up.

Product of Array Except Self

Brute Force

Prefix × Suffix Products

More Arrays & Hashing practice