Optimal Python Solution for Product of Array Except Self (Interview Script)

2025-10-03

The Logic

• Division is disallowed, so we cannot compute total product directly.
• Each position needs the product of all elements to its left and right.
• Prefix and suffix products allow this in linear time without extra arrays.

Implementation / Diagram

Key Invariant

At index i, the result equals the product of all elements before i times the product of all elements after i.

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

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

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

    return result