[Top Interview 150] 238. Product of Array Except Self
Solution)
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# Initialization
res = [1] * len(nums)
pre = 1
# Multiply prefixes
for i in range(len(nums)):
res[i] *= pre
pre *= nums[i]
post = 1
# Multiply postfixes
for i in range(len(nums)-1, -1, -1):
res[i] *= post
post *= nums[i]
return res
Problem: LeetCode
Reference: NeetCode
Time Complexity: O(n)
Space Complexity: O(1)
Explanation)
Once you understand the concept of prefixes and postfixes, the problem will look much easier.
Say nums is [1, 2, 3, 4], then the output will be [24, 12, 8, 6].
Each element of the output is a product of prefixes and postfixes of nums.
First, we initialize an array of 1's with a length of nums.
Then, we multiply each element's prefixes to that array.
Once we multiplied prefixes, we multiply each element's postfixes and return that array.
Initialization)
Because we're multiplying prefixes and postfixes, our initial values of res is one.
If we were looking for sums, it would have been zero.
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
Multiplying Prefixes)
0th element of nums doesn't have a prefix and only has a postfix.
For example, if nums is [1, 2, 3, 4], the element 1 doesn't have a prefix and has a postfix of 24.
Even though there isn't a prefix, since we're looking for a multiplication, our initial value of pre is one.
Through a for-loop, we first multiply an element of res by pre.
Then, we update pre by multiplying the current element of nums.
If nums is [1, 2, 3, 4], pre would become 1 -> 1 -> 2 -> 6.
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
pre = 1
for i in range(len(nums)):
res[i] *= pre
pre *= nums[i]
Multiplying Postfixes)
Once we multiplied the prefixes, we then multiply the postfixes.
The logic is exactly the same, just backwards.
If nums is [1, 2, 3, 4], the postfixes would be 1 -> 4 -> 12 -> 24.
After all the multiplications are completed, return res.
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
pre = 1
for i in range(len(nums)):
# Multiplying Prefix
post = 1
for i in range(len(nums)-1, -1, -1):
res[i] *= post
post *= nums[i]
return res
This was a new concept for me, so watching NeetCode's solution wasn't so embarassing haha. For this solution, you can do both prefix/postfix multiplications in one for-loop, but seperating it looks more readable.