Product except self in Python

Why this lesson matters

A common exercise gives you a list of whole numbers and asks for a second list of the same length. Each spot in the new list holds the product of every number in the input except the number at that same spot. A product is what you get when you multiply numbers together, so the product of 2, 3 and 4 is 24.

The exercise looks easy until you see the rule that makes it interesting: you may not use division. The first idea most people try is to multiply all the numbers together once, then divide that total by each number in turn. That idea breaks as soon as the list contains a zero, because you cannot divide by zero.

This lesson shows a method that uses no division. It makes two passes over the list, one from left to right and one from right to left. It works with zeros, negative numbers and lists with only one value. The same two-direction idea is useful any time a question asks for the combined effect of everything except one item.

Python lists are the tool here. You will need to know that a list has a length from len, that the first position is index 0, and that the last position is len(nums) - 1. If you have not used these yet, the earlier lessons in this module cover them.

The problem in plain words

Take the list [1, 2, 3, 4]. The positions, called indexes, are 0, 1, 2 and 3. Index 0 holds 1, index 1 holds 2, and so on.

For each index, the answer is the product of every value except the one at that index. The table below shows the work for each spot.

So the answer for [1, 2, 3, 4] is [24, 12, 8, 6]. The input is not changed. A new list holds the answer.

The answer at each index is built from two parts. The part to the left of the index is called the prefix. The part to the right is called the suffix. For index 2 in the example, the prefix is 1 times 2, which is 2, and the suffix is 4. Multiply them and you get 8, which matches the table.

Why division is not the answer

Here is the division idea written as Python code, so you can see where it fails. It multiplies all the values into one total, then divides the total by each value.

def by_division(nums):
    total = 1
    for v in nums:
        total *= v                  # multiply every value together
    return [total // v for v in nums]   # remove this value by dividing it out

The loop for v in nums reads the list one value at a time, from the first position to the last. The // operator is floor division, which divides and keeps only the whole part. Here every division is exact, so the whole part is the full answer.

With [1, 2, 3, 4] this works, because the total is 24 and 24 divided by each value gives the right answer. Now try [1, 2, 0, 4]. The total is 0. The value at index 2 is 0, so the code divides by zero. Python stops with this error:

ZeroDivisionError: division by zero

The message text can differ by Python version, but the error type is always ZeroDivisionError. Dividing by zero has no answer, so Python raises an exception. An exception is an error that stops the code unless you catch it. The two-pass method below avoids this problem.

The idea: a running prefix and a running suffix

Here is the plan. Walk the list from left to right and keep a running product of everything you have passed so far. Before you update the running product with the current value, copy it into the answer. At that moment the running product holds only the values to the left, so the copy is the prefix.

Then walk the list from right to left with a second running product. This one covers the values to the right. Multiply the answer at each spot by this running product, then update the running product with the current value. The answer now holds prefix times suffix.

Two words need a plain definition before the code. The running product is a single variable that starts at 1 and changes as you move through the list. The empty product is 1. When no values are to the left of index 0, the product of those values is 1, because multiplying by nothing leaves a number unchanged. This is why the running product starts at 1, not 0. If it started at 0, every answer would be 0.

Here are the two lists that the idea uses, written out for [1, 2, 3, 4]. The prefix list holds the product of values before each index. The suffix list holds the product of values after each index.

index:   0   1   2   3
nums:    1   2   3   4
prefix:  1   1   2   6     product of values before the index
suffix: 24  12   4   1     product of values after the index
answer:  24  12   8   6     prefix times suffix, position by position

Check index 0. Nothing is before it, so the prefix is 1. The values after it are 2, 3 and 4, and their product is 24. The answer is 1 times 24, which is 24. Check index 3. The values before it are 1, 2 and 3, so the prefix is 6. Nothing is after it, so the suffix is 1. The answer is 6.

Version 1: two helper lists

The first version stores the prefix and suffix in their own lists. It takes more memory, but each step is easy to see, so start here.

def with_two_lists(nums):
    n = len(nums)                       # how many values there are
    prefix = [0] * n
    suffix = [0] * n
    result = [0] * n
 
    running = 1                         # empty product
    for i in range(n):
        prefix[i] = running             # product of nums[0] up to nums[i - 1]
        running *= nums[i]              # add nums[i] to the running product
 
    running = 1                         # start again from the right
    for i in range(n - 1, -1, -1):
        suffix[i] = running             # product of nums[i + 1] up to the last value
        running *= nums[i]
 
    for i in range(n):
        result[i] = prefix[i] * suffix[i]   # combine the two parts
    return result

The first loop goes left to right and fills prefix. The second loop goes right to left and fills suffix. The third loop multiplies the two lists position by position. Each loop has one job, which makes the code easy to check.

The range range(n - 1, -1, -1) counts down from the last index to 0. The stop value is -1, because a range never includes its stop value.

Notice the variable n. It holds len(nums), the number of values. Reading the length into a variable once is a common habit. It also makes the loop conditions easier to read.

Version 2: one answer list and one running value per pass

The second version drops the two helper lists. It writes the prefix straight into the answer list during the first pass, then multiplies in the suffix during the second pass. The total memory is the answer list plus two single numbers.

Output:

input  [1, 2, 3, 4]
output [24, 12, 8, 6]
input  [0, 4, 0]
output [0, 0, 0]

Notice the operator *= in the second loop. It means "multiply the stored value by this and save the result." The line result[i] *= suffix is short for result[i] = result[i] * suffix. It keeps the prefix that the first loop stored and multiplies in the suffix.

Trace the two loops on [1, 2, 3, 4]. The first loop changes only result and prefix.

pass 1, left to right, prefix starts at 1
i=0: result[0] = 1        prefix becomes 1 * 1 = 1
i=1: result[1] = 1        prefix becomes 1 * 2 = 2
i=2: result[2] = 2        prefix becomes 2 * 3 = 6
i=3: result[3] = 6        prefix becomes 6 * 4 = 24
after pass 1, result is [1, 1, 2, 6]
 
pass 2, right to left, suffix starts at 1
i=3: result[3] = 6 * 1 = 6     suffix becomes 1 * 4 = 4
i=2: result[2] = 2 * 4 = 8     suffix becomes 4 * 3 = 12
i=1: result[1] = 1 * 12 = 12   suffix becomes 12 * 2 = 24
i=0: result[0] = 1 * 24 = 24   suffix becomes 24 * 1 = 24
after pass 2, result is [24, 12, 8, 6]

Each line of the second pass reads the value that the first pass left behind. That is why the first pass must come first.

Worked examples of rising difficulty

Example 1: two values

Take [2, 5]. For index 0, the only other value is 5, so the answer is 5. For index 1, the only other value is 2, so the answer is 2. The output is [5, 2]. This example shows that each spot gets the product of the rest, and with two values the rest is one number.

Example 2: zeros and negative numbers

Take [-1, 1, 0, -3, 3]. Here is the output from the code:

input  [-1, 1, 0, -3, 3]
output [0, 0, 9, 0, 0]

Index 2 holds the zero. Its answer is the product of the other four values, which is -1 times 1 times -3 times 3. Two negative signs make a positive, so the product is 9.

Every other index includes the zero at index 2 in its product, so each of those answers is 0. The method handles this without any special case. A zero only affects the spots whose product includes it, and the running products do that work by themselves.

When two or more zeros appear, every answer is 0, because every spot has at least one zero among the other values. The list [0, 4, 0] gives [0, 0, 0]. Index 1 holds the 4, and its product includes both zeros, so its answer is 0.

Example 3: one value

Take [7]. There are no other values, so the product of the others is the empty product, which is 1. The output is [1]. Many beginners expect an error here, but the code returns 1 because the running product starts at 1 and the loops still run once.

Example 4: a longer list

Take [2, 3, 4, 5]. Work out the prefix and suffix for each index, then multiply them.

index:   0   1   2   3
nums:    2   3   4   5
prefix:  1   2   6  24     product of values before the index
suffix: 60  20   5   1     product of values after the index
answer: 60  40  30  24     prefix times suffix

Index 1 has prefix 2 and suffix 4 times 5, which is 20. Its answer is 2 times 20, which is 40. The method printed:

input  [2, 3, 4, 5]
output [60, 40, 30, 24]

The same two passes handle a list of any length. The work grows in step with the number of values, because each value is visited a fixed number of times.

Checking the answer

A good habit is to write a slow version that is easy to trust, then compare the two on many inputs. The slow version multiplies every other value for each index. It does more work, but there is little to get wrong.

Output:

random trials 2000 failures 0

The inner if j != i skips the position that the answer is about. The != operator means "not equal to."

The test compares the two versions on 2000 random lists. Each list has between 1 and 6 values, and each value is between -5 and 5. The random generator is seeded with 1, so the same lists are made every time the test runs.

This test does not prove the code is correct for every input. It does show that the fast version and the slow version agree on the inputs tried.

Large products

Python integers have no size limit. A product can grow as large as the memory allows, and it never wraps around to a wrong small value. Each answer for [100000, 100000, 100000] is 100000 times 100000. The block below prints that value and the product of all three numbers.

Output:

10000000000
1000000000000000

Other languages store an integer in a fixed number of bits, and a product past that limit wraps around to a small wrong value with no error. A Java int has 32 bits, and the same input gives wrong numbers there. Python avoids that problem by design, so the method needs no special type. A very long list of large numbers still takes more time and memory, but the answers stay correct.

Common mistakes

Dividing by the values

This is the mistake covered earlier in the lesson. Any list with a zero makes it raise ZeroDivisionError. Even without a zero, it breaks the rule of the exercise.

Starting the running product at 0

If you write prefix = 0, every product is 0, because any number times 0 is 0. The running product must start at 1. Here is what goes wrong with [1, 2, 3, 4] if you start at 0. Every value in the first pass is 0, so the answer is all zeros.

Output:

[0, 0, 0, 0]

Using = instead of *= in the second pass

The second pass must multiply into the prefix that is already stored. If you write result[i] = suffix instead of result[i] *= suffix, the prefix from the first pass is thrown away. Running that version on [1, 2, 3, 4] gives:

Output:

[24, 12, 4, 1]

Compare this with the correct [24, 12, 8, 6]. The first two answers happen to match, but the last two are wrong: index 2 gives 4 instead of 8, and index 3 gives 1 instead of 6.

Running the suffix loop past the end

The suffix loop must start at n - 1, which is the last valid index. Starting at n asks for a position that does not exist. The code below runs on [1, 2, 3] and uses range(n, -1, -1) in the loop:

def product_except_self(nums):
    n = len(nums)
    result = [0] * n
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n, -1, -1):          # wrong: starts one past the end
        result[i] = suffix
        suffix *= nums[i]
    return result
 
print(product_except_self([1, 2, 3]))

Python reports this error:

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(product_except_self([1, 2, 3]))
          ~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^
  File "main.py", line 10, in product_except_self
    result[i] = suffix
    ~~~~~~^^^
IndexError: list assignment index out of range

The message names the failing line, and the ^^^ marks show that the write to result[i] failed. The loop reached index 3, and the list has length 3, so the valid indexes are 0, 1 and 2. Read the loop bounds to find the bad start value.

Forgetting that a single value has an empty product

Some people write special code for the case of one value and return an error or an empty list. The method above already handles it, and returns 1 for a single value. A special case is not needed.

Practice

Try each one before you read the answer. Save each program as main.py and run it to check your answer.

Exercise 1

Work out the answer for [2, 3, 4] by hand. Write the answer as a list.

Show the answer

Index 0 holds 2, and the other values are 3 and 4, so the answer is 3 times 4, which is 12. Index 1 holds 3, and the others are 2 and 4, so the answer is 8. Index 2 holds 4, and the others are 2 and 3, so the answer is 6. The result is [12, 8, 6].

Exercise 2

Without running code, say what product_except_self returns for [0, 0, 5].

Show the answer

The result is [0, 0, 0]. Index 0 includes the zero at index 1 in its product. Index 1 includes the zero at index 0. Index 2 includes both zeros, because they are among the other values. Every answer has at least one zero in its product, so every answer is 0.

Exercise 3

Write a function prefix_products that takes a list and returns a list where result[i] is the product of nums[0] up to nums[i], including nums[i]. For [1, 2, 3, 4], it should return [1, 2, 6, 24].

Show the answer

Output:

[1, 2, 6, 24]
[2, 6, 24]

The running product is updated first, then stored. This is the opposite order from the prefix loop in product_except_self, which stores first and multiplies second. When the code stores after multiplying, the value at index i includes nums[i].

Exercise 4

The method above uses an extra list for the answer. Explain why the answer list does not count as extra space in the usual meaning of the exercise, and what the extra memory is in the method.

Show the answer

The exercise asks for the answer as a new list, so the answer list is the required output and is not counted as extra working space. The working memory is the two running variables, prefix and suffix, plus the loop index and the length. Those take a fixed amount of memory, no matter how long the list is. The version with two helper lists uses two more lists of the same length, which is extra working space that grows with the input.

Exercise 5

Trace product_except_self([3, 0, 2]) by hand, first writing the prefix values and then the suffix values. Check each answer by multiplying the other two values directly.

Show the answer

The first pass stores the prefix values [1, 3, 0], because the running product is 1, then 3, then 0. The second pass starts with suffix at 1. At index 2 it multiplies 0 by 1, giving 0, and suffix becomes 2. At index 1 it multiplies 3 by 2, giving 6, and suffix becomes 0. At index 0 it multiplies 1 by 0, giving 0. The result is [0, 6, 0]. Check it directly: index 0 has the others 0 and 2, which give 0. Index 1 has the others 3 and 2, which give 6. Index 2 has the others 3 and 0, which give 0.

Summary

• The answer at each index is the product of the values to its left, the prefix, times the product of the values to its right, the suffix.
• Two passes build the answer without division: one left to right to store prefixes, and one right to left to multiply in suffixes.
• The running products start at 1, which is the empty product, so zeros and single-value lists work without special cases.
• Division fails when a zero is present, and Python raises ZeroDivisionError.
• Python integers do not overflow, so the same method gives exact answers for large products.
• Check the fast method against a slow, obviously correct method on many random inputs.