Product of Array Except Self
- 2 min read
- Array
- LC-Medium
3 years ago
Solution
- Since we can't use the division operator, we need to just use the multiplication.
- If you look closely, for each number
nums[i], the value inans[i]is just a product of the numbers that come before it and the numbers that come after it. - When doing a for loop, since we should not multiply a number by itself, we first multiply by the prefix, and then update the prefix by multiplying it with the current number.
- This order is important!!
- We don't have to use auxiliary arrays here, although it helps to see how the answer works when you see the prefix and postfix arrays on top of one another:
# input [1, 2, 3, 4]
# prefix [1, 1, 2, 6]
# postfix [24, 12, 4, 1]
# mults. [24, 12, 8, 6] this is your answer
- Each value in
ans[i]is justprefix[i] * postfix[i]
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def productExceptSelf(self, nums: List[int]) -> List[int]:
ans = [1] * len(nums)
prefix = 1
for i in range(1, len(nums)):
prefix *= nums[i - 1]
ans[i] *= prefix
postfix = 1
for i in range(len(nums) - 2, -1, -1):
postfix *= nums[i + 1]
ans[i] *= postfix
return ans