Medium

Product of Array Except Self

030

Given an integer array nums, return an array where output[i] is the product of every value in nums except nums[i]. Do not use division.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3,
    4
  ]
}

Output
[
  24,
  12,
  8,
  6
]

FUNCTION SHAPE

nums: intArray→intArray

SOLUTION NOTE

Product except self = prefix_product[i-1] × suffix_product[i+1]. Two passes: first builds prefix products into result, second multiplies by suffix products. O(1) extra space by computing on the fly.

Reveal reference solution +

pythonREFERENCE

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

    # First pass: prefix products (left of each index)
    prefix = 1
    for i in range(n):
        res[i] = prefix
        prefix *= nums[i]

    # Second pass: multiply by suffix products (right of each index)
    suffix = 1
    for i in range(n - 1, -1, -1):
        res[i] *= suffix
        suffix *= nums[i]

    return res

TimeO(n)

SpaceO(1) extra (output not counted)

Open on LeetCode ↗