Product of Array Except Self

Q: Why is division not allowed in Product of Array Except Self?

Dividing the total product by nums[i] breaks when the array holds a zero, because the total is 0 and the zero's own index would need a division by 0. Making it work needs a count of the zeros and special cases. The rule pushes you toward prefix and suffix products, which handle zeros with no special case at all.

MediumPrefix sum

+10

You get an array of integers nums. Return an array answer of the same length, where answer[i] is the product of every element of nums except the one at index i. Do it in O(n) time and without using division.

Function

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: the array of integers, with at least two elements
Returnsinteger-array: an array whose value at index i is the product of all elements except nums[i]

Constraints

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
The product of all the nonzero values in nums fits in a 32-bit signed integer, so every product you build along the way fits too.

Examples

Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
Explanation: Leaving out the 2 leaves 3 × 4 × 5 = 60, and leaving out the 5 leaves 2 × 3 × 4 = 24. The middle two work the same way: 2 × 4 × 5 = 40 and 2 × 3 × 5 = 30.

+14 hidden tests on Submit

Follow-up

Can you use only O(1) extra space, not counting the array you return?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The product of everything except nums[i] is the product of the values to its left times the product of the values to its right. Dividing the total product by nums[i] looks shorter, but it is not allowed here and it breaks on zeros, where the total is 0. Prefix and suffix products give every left and right product in two passes, so the answer costs O(n) time. The output array can hold the left products, and one variable carries the right product, so no other array is needed.

Multiply the others for each index

Correct, but does not finish on the largest tests

Intuition

Follow the definition. For each index i, start a product at 1 and multiply in every nums[j] whose index j is not i. Skipping that index, rather than dividing it out later, keeps zeros harmless: in [-2, 5, 0, 3] the product for index 2 never sees the 0 and comes out as -30.

It is correct, but it repeats work. The products for index 0 and index 1 share every value except two, and you multiply all of them again anyway. Each of the n positions costs n-1 multiplications, about 10^8 in total when n = 10^4. C gets through that in a fraction of a second, but Python, Ruby or R take far too long.

Algorithm

Create an answer array of length n.
For each index i, set product to 1.
Multiply product by every nums[j] whose index j is not i.
Store product at index i of the answer.
Return the answer.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Prefix and suffix product arrays

Intuition

Split the product for index i in two: the values before i and the values after it. Call those products before[i] and after[i]. Then answer[i] = before[i] × after[i], and nums[i] is left out without any division.

Each array grows from its neighbour with one multiplication. before[0] is 1, the product of no values, and before[i] = before[i-1] × nums[i-1]. From the other end, after[n-1] is 1 and after[i] = after[i+1] × nums[i+1]. For [2, 3, 4, 5] you get before = [1, 2, 6, 24] and after = [60, 20, 5, 1], and multiplying them position by position gives [60, 40, 30, 24].

Three passes of n steps make O(n) time. The two helper arrays cost O(n) extra memory, which the next approach removes.

Algorithm

Fill before from the left: before[0] = 1, then each entry is the previous entry times the previous value.
Fill after from the right: after[n-1] = 1, then each entry is the next entry times the next value.
Set answer[i] to before[i] × after[i] for every index.
Return answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Left products in the answer, one running right product

Intuition

You never need the whole after array at once. Walking from the right end, the product of the values to the right of i is a single number. Keep it in a variable right and update it with one multiplication per step.

So write the left products straight into the answer array in a first pass. In a second pass from the right, multiply answer[i] by right, and only then multiply right by nums[i]. The order matters: when you use right at index i, it must not include nums[i] yet.

For [2, 3, 4, 5], the first pass leaves [1, 2, 6, 24]. The second pass uses right = 1, 5, 20, 60 at indices 3, 2, 1, 0 and turns the array into [60, 40, 30, 24]. The time is still O(n), and besides the array you return, the extra memory is one variable: O(1).

Algorithm

Set answer[0] = 1, then from left to right set answer[i] = answer[i-1] × nums[i-1].
Set right to 1.
From the last index down to 0, multiply answer[i] by right.
Then multiply right by nums[i].
Return answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Pitfalls and edge cases

The bugs here come from zeros, from the order of the two updates in the second pass, and from the edges of the array.

Dividing the total product by nums[i] fails once a 0 appears. For [-2, 5, 0, 3] the total is 0, and index 2 would need 0 divided by 0. Counting zeros can patch it, but the problem rules out division anyway.
Multiplying right by nums[i] before you use it puts nums[i] into its own product. For [2, 3, 4, 5] the last value becomes 120 instead of 24.
Starting the left products at nums[0] instead of 1. Nothing stands to the left of index 0, so its left product is the empty product, 1, and answer[0] ends up as the product of the values to its right only.
Loop bounds: the left pass reads nums[i-1], so it starts at index 1. A suffix array reads nums[i+1], so it starts at index n-2.
Two zeros make every answer 0. One zero makes every answer 0 except the one at the zero's own index. Test both cases before you trust your code.

Frequently asked questions4

What is the time complexity of Product of Array Except Self?

The prefix and suffix solution runs in O(n) time: one pass from the left and one from the right. With the left products stored in the output array and a single running right product, it needs O(1) extra space besides the output. Multiplying all the other values for every index takes O(n²) time.

Why is division not allowed in Product of Array Except Self?

Dividing the total product by nums[i] breaks when the array holds a zero, because the total is 0 and the zero's own index would need a division by 0. Making it work needs a count of the zeros and special cases. The rule pushes you toward prefix and suffix products, which handle zeros with no special case at all.

Does the output array count as extra space?

No. You have to return the answer anyway, so the usual convention leaves it out of the space count. Storing the left products in it and keeping the right product in one variable therefore counts as O(1) extra space.

How does Product of Array Except Self handle zeros?

With prefix and suffix products, zeros need no special case. Any left or right product that reaches past a zero is 0, and the product for the zero's own index skips it. With two or more zeros, every product contains one, so every answer is 0.

Python

def productExceptSelf(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [2, 3, 4, 5]

Expected

[60, 40, 30, 24]

Product of Array Except Self

Function

Constraints

Examples

Hints

Solution

Multiply the others for each index

Prefix and suffix product arrays

Left products in the answer, one running right product

Pitfalls and edge cases

Frequently asked questions4

Similar problems