Prefix and Suffix Products

Some array problems require combining information from the left and right side of each index.

Idea

• prefix[i]: product of values before i
• suffix[i]: product of values after i
• answer at i is prefix[i] * suffix[i]

You can do this in O(n) time and O(1) extra space (excluding output).

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

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

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

    return result

Why it works

Each index gets all multiplication from the left pass and right pass, excluding itself.