MediumBlind75Array

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Examples

Input
nums = [1,2,3,4]
Output
[24,12,8,6]

answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, etc.

Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]

Products involving 0 become 0.

Constraints

  • •2 <= nums.length <= 10^5
  • •-30 <= nums[i] <= 30
  • •The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Approaches

For each element, compute the product of all other elements.

CodeT: O(n^2) | S: O(1)
def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                result[i] *= nums[j]
    return result

Compute prefix products and suffix products, then multiply them.

CodeT: O(n) | S: O(n)
def product_except_self(nums):
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n
    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)]

Use the result array for prefix products, then traverse backwards with a running suffix product.

Diagram

nums=[1,2,3,4] Prefix pass: result=[1,1,2,6] Suffix pass: result=[24,12,8,6]
CodeT: O(n) | S: O(1)
def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    for i in range(1, n):
        result[i] = result[i-1] * nums[i-1]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

Complexity Comparison

Brute Force
T: O(n^2)S: O(1)

For each element, compute the product of all other elements.

Prefix and Suffix Products
T: O(n)S: O(n)

Compute prefix products and suffix products, then multiply them.

Single Pass with Output Array
T: O(n)S: O(1)

Use the result array for prefix products, then traverse backwards with a running suffix product.

Common Mistakes

Using division which fails when there are zeros in the array

Not handling negative numbers correctly

Off-by-one errors when computing prefix/suffix products

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems