Product of Array Except Self

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Each product is guaranteed to fit in a 32-bit integer.

Follow-up: Could you solve it in $O(n)$ time without using the division operation?

Approach

Build the result using prefix and suffix products. First, set output[i] to the product of all elements before i by sweeping left to right. Then sweep right to left with a running suffix product and multiply it into output[i]. This handles zeros naturally because every position excludes itself without division.

Why It Works

For each index i), the product of all elements except nums[i]equals (product of elements beforei) * (product of elements after i`). The two passes compute exactly these two components for every index, so the final product is correct.

Complexity

• Time: O(n)
• Space: O(1) extra (excluding the output array)

Reference Implementation (Python)

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

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

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

        return output