DSA Product of Array Except Self

The problem

Product except self builds an answer list from a list of numbers. The entry at each index is the product of every value except the one at that index. The value at the index is the one thing left out.

The input is a list of numbers. The output is a list of the same length. The two lists align by index.

cases = [
    ([1, 2, 3, 4], [24, 12, 8, 6]),
    ([1, 2, 0, 4], [0, 0, 8, 0]),
    ([-1, 2, -3], [-6, 3, -2]),
    ([3, 5], [5, 3]),
]
for values, expected in cases:
    print("values", values, "answer:", expected)

Read one row at a time. In the first row, index 0 multiplies 2, 3 and 4 and gets 24. In the second row the zero at index 2 is left out of its own entry only, so that entry is 8 while the others include the zero.

Intuition: divide the total product — the trap

The first idea computes the product of everything once. Each answer is then that total divided by the value at the index. One pass, one division per entry, and the method looks finished.

The trap is a zero. A zero anywhere makes the total zero. Every division then divides by a value, and at the zero index itself the division is by zero. A second zero breaks even the rescue attempts, because the total no longer says which entries should be zero.

values = [1, 2, 0, 4]
total = 1
for value in values:
    total *= value
print("total product:", total)
for i, value in enumerate(values):
    if value == 0:
        print("index", i, "needs total / 0: undefined")
    else:
        print("index", i, "total /", value, "=", total // value)

Every non-zero index gets 0, which happens to be right, and the zero index gets nothing at all. Its true answer is 8, the product of the others. A method that never divides avoids the whole failure.

Brute force: recompute each entry from scratch

A straightforward method needs no division. For each index, it loops over the whole list and multiplies everything except that index. Each entry is computed independently.

The answers are always right. The cost is the repetition: each entry re-multiplies values that the neighbouring entry just multiplied. A counter on the multiplications shows the bill.

def product_slow(values):
    answer = []
    multiplications = 0
    for skip in range(len(values)):
        product = 1
        for i, value in enumerate(values):
            if i != skip:
                product *= value
                multiplications += 1
        answer.append(product)
    return answer, multiplications

for values in ([1, 2, 3, 4], [1, 2, 0, 4]):
    answer, multiplications = product_slow(values)
    print(values, "->", answer, "multiplications:", multiplications)

Four values cost twelve multiplications: four entries times three factors each. The count grows with the square of the length. Most of those products are shared work waiting to be reused.

The optimal solution: left products meet right products

Precompute two lists in two passes: the product of the values before each index, and the product of the values after it, so each answer is one multiplication of its left and right parts. No division appears anywhere.

def product_except_self(values):
    left = []
    running = 1
    for value in values:
        left.append(running)
        running *= value
    right = [1] * len(values)
    running = 1
    for i in range(len(values) - 1, -1, -1):
        right[i] = running
        running *= values[i]
    answer = []
    for i in range(len(values)):
        answer.append(left[i] * right[i])
    return answer

for values in ([1, 2, 3, 4], [1, 2, 0, 4], [-1, 2, -3], [3, 5]):
    print(values, "->", product_except_self(values))

All four cases pass. The zero case needs no branch. The first entry of the left list is 1, the product of nothing, and the last entry of the right list is 1 for the same reason.

Walkthrough: [2, 3, 4, 5] pass by pass

Watch the two lists fill for one input. The left pass runs forwards and stores the running product before multiplying. The right pass runs backwards and does the same from the other end.

values = [2, 3, 4, 5]
left = []
running = 1
for value in values:
    left.append(running)
    running *= value
    print("left so far:", left)
right = [1] * len(values)
running = 1
for i in range(len(values) - 1, -1, -1):
    right[i] = running
    running *= values[i]
    print("right so far:", right)
answer = [left[i] * right[i] for i in range(len(values))]
print("answer:", answer)

At index 1 the left part is 2 and the right part is 20. Their product is 40, which is 2 times 4 times 5: everything except the 3 at index 1. Every index reads its answer off the same two lists.

Complexity

Time is O(n) for a list of length n: two passes build the lists and one short pass combines them, so each value is multiplied a fixed number of times.

Space is O(n) beyond the answer: the left and right lists each hold one entry per value, aligned by index.

def count_slow(n):
    return n * (n - 1)

def count_fast(n):
    left_steps = n
    right_steps = n
    combine_steps = n
    return left_steps + right_steps + combine_steps

for n in (4, 10, 100):
    print("length", n, "brute force multiplications:", count_slow(n), "two-pass multiplications:", count_fast(n))

At length 100 the brute force pays 9,900 multiplications and the two passes pay 300. The printed counts grow in a curve for one method and a straight line for the other.

Edge cases and pitfalls

One zero zeroes every entry except its own. Two zeros zero every entry without exception, because each entry then includes at least one zero. Neither case needs a branch in the two-pass method.

A list of one value answers [1]. The single entry multiplies the values at all other indexes, and there are none. The product of nothing is 1, the same 1 that seeds both passes.

def product_except_self(values):
    left = []
    running = 1
    for value in values:
        left.append(running)
        running *= value
    right = [1] * len(values)
    running = 1
    for i in range(len(values) - 1, -1, -1):
        right[i] = running
        running *= values[i]
    answer = []
    for i in range(len(values)):
        answer.append(left[i] * right[i])
    return answer

print("one zero:", product_except_self([2, 0, 3]))
print("two zeros:", product_except_self([0, 4, 0]))
print("single value:", product_except_self([7]))
print("pair:", product_except_self([3, 5]))
print("empty:", product_except_self([]))

One pitfall is seeding a running product with 0 instead of 1. Every later product then collapses to 0. The seed must be the product of nothing, and that product is 1.