← Back to Python Examples

Product of Array Except Self

A constraint that rules out the obvious answer forces an elegant prefix/suffix solution.

Contents

  1. The Problem
  2. The Obvious Approach (and Why It Fails)
  3. Prefix and Suffix Products
  4. The O(n) Solution
  5. Optimized — O(1) Extra Space

1. The Problem

Given an integer array, return a new array where each element is the product of all other elements in the original array. You must do this without using division, in O(n) time.

# [1, 2, 3, 4]  →  [24, 12, 8, 6]
#   24 = 2×3×4      (everything except index 0)
#   12 = 1×3×4      (everything except index 1)
#    8 = 1×2×4      (everything except index 2)
#    6 = 1×2×3      (everything except index 3)

2. The Obvious Approach (and Why It Fails)

Multiply all elements together, then divide by each element. Simple — but division is explicitly forbidden, and it breaks completely when any element is zero.

# What if nums = [1, 0, 3, 4]?
# Total product = 0.  Dividing by 0 is undefined.
# Division won't save you even if it were allowed.

3. Prefix and Suffix Products

For each index i, the answer is the product of everything to the left of i multiplied by the product of everything to the right of i.

# nums =  [1,  2,  3,  4]
#
# prefix[i] = product of nums[0..i-1]
# prefix = [1,  1,  2,  6]
#           ↑   ↑   ↑   ↑
#       nothing 1  1×2  1×2×3
#
# suffix[i] = product of nums[i+1..end]
# suffix = [24, 12,  4,  1]
#           ↑    ↑   ↑   ↑
#        2×3×4 3×4   4  nothing
#
# result[i] = prefix[i] × suffix[i]
# result = [1×24, 1×12, 2×4, 6×1] = [24, 12, 8, 6]  ✓

4. The O(n) Solution — Two Arrays

def product_except_self(nums):
    n = len(nums)
    prefix = [1] * n
    suffix = [1] * n

    # Build prefix products
    for i in range(1, n):
        prefix[i] = prefix[i - 1] * nums[i - 1]

    # Build suffix products
    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)]

print(product_except_self([1, 2, 3, 4]))   # [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]

Time: O(n). Space: O(n) for the two arrays.

5. Optimized — O(1) Extra Space

Use the output array itself to hold prefix products, then multiply in suffix products in a second pass using a single running variable.

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

    # Pass 1: fill result with prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Pass 2: multiply in suffix products from the right
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

print(product_except_self_optimized([1, 2, 3, 4]))  # [24, 12, 8, 6]
Time: O(n). Space: O(1) extra (the output array itself doesn't count toward space complexity by convention). This is the answer interviewers are looking for as a follow-up to the two-array solution.