Product of Array Except Self
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
- 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 ≤ 104-30 ≤ nums[i] ≤ 30- The product of all the nonzero values in
numsfits 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. Leaving out the 3, the 4 or the 5 gives 40, 30 and 24 the same way.
- Input
- nums = [-2, 5, 0, 3]
- Output
- [0, 0, -30, 0]
- Explanation
- Every product that includes the 0 is 0. Only the product for index 2 leaves the 0 out, and it is -2 × 5 × 3 = -30.
- Input
- nums = [0, 4, 0, -1]
- Output
- [0, 0, 0, 0]
- Explanation
- With two zeros, every product still includes at least one of them, so every value in the answer is 0.
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.
Multiplying all the other values for each index works, but with 10,000 values that is about 100 million multiplications, and most of them repeat. What does the product for index
ishare with the product for indexi + 1?Everything except
nums[i]splits into the values to its left and the values to its right. If you knew the product of every prefix and of every suffix, each answer would take one multiplication.Fill the answer array from the left with the product of the values before each index, starting from 1. Then walk from the right with one running product of the values after the index: multiply it into the answer first, and only then multiply in
nums[i].
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. Prefix and suffix products give all of them in two passes without division, so zeros need no special case. The output array can hold the left products, and one variable the right product.
Multiply the others for each index
Correct, but does not finish on the largest tests
Intuition
For each index i, start a product at 1 and multiply in every nums[j] with j not equal to i. Skipping index i, rather than dividing it out later, keeps zeros harmless. Each of the n positions costs n-1 multiplications, about 10^8 when n = 10^4, and the products for neighbouring indices share all but two of their values.
Algorithm
- Create an answer array of length n.
- For each index
i, setproductto 1. - Multiply
productby everynums[j]whose indexjis noti. - Store
productat indexiof 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 answerPrefix and suffix product arrays
Intuition
Call the product of the values before index i before[i], and the product of the values after it 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]; after mirrors it from the right end. For [2, 3, 4, 5] you get before = [1, 2, 6, 24] and after = [60, 20, 5, 1], whose products are [60, 40, 30, 24]. The two helper arrays cost O(n) extra memory.
Algorithm
- Fill
beforefrom the left:before[0] = 1, then each entry is the previous entry times the previous value. - Fill
afterfrom the right:after[n-1] = 1, then each entry is the next entry times the next value. - Set
answer[i]tobefore[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
Walking from the right end, the product of the values after index i is a single number, so you never need the whole after array. Keep it in a variable right and update it with one multiplication per step.
Write the left products straight into the answer array. On the way back, multiply answer[i] by right before you multiply right by nums[i]: when you use right at index i, it must not include nums[i] yet. For [2, 3, 4, 5], right is 1, 5, 20 and 60 at indices 3, 2, 1 and 0. Besides the array you return, the extra memory is one variable.
Algorithm
- Set
answer[0] = 1, then from left to right setanswer[i] = answer[i-1] × nums[i-1]. - Set
rightto 1. - From the last index down to 0, multiply
answer[i]byright. - Then multiply
rightbynums[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
- Dividing the total product by
nums[i]. For[-2, 5, 0, 3]the total is 0, and index 2 would need 0 divided by 0. - Multiplying
rightbynums[i]before you use it, which putsnums[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 left of index 0, so its left product is 1; otherwise[2, 3, 4, 5]gives 120 at index 0 instead of 60. - Loop bounds. The left pass reads
nums[i-1], so it starts at index 1; a suffix array readsnums[i+1], so it starts at index n-2.
Frequently asked questions3
What is the time complexity of Product of Array Except Self?
The prefix and suffix solution runs in O(n) time, one pass from each end. With the left products in the output array and one 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: the total is 0, and the zero's own index needs a division by 0. Fixing that takes a count of zeros and special cases. Prefix and suffix products handle zeros with no special case.
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 counts as O(1) extra space.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def productExceptSelf(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [2, 3, 4, 5]
Expected Output
[60, 40, 30, 24]