Product of array except self

Link: https://leetcode.com/problems/product-of-array-except-self/

Solution:

Topics: prefix sums

Intuition
Not a very difficult problem…basically we borrow the idea from prefix and postfix sums, but instead of sums we make it the running product at every i . Then to get the product of the array except self, we can perform prefix[i-1]*postfix[i+1]. Thats all there is to it because multiplication is commutative.

Implementation

def product_except_self(nums):
	n = len(nums)
	pre = [-1] * n
	post = [-1] * n
	res = [-1] * n
 
	pre[0] = nums[0]
	for i in range(1, n):
		pre[i] = pre[i-1]*nums[i]
	post[-1] = nums[-1]
	for i in range(n-2, -1, -1):
		post[i] = post[i+1]*nums[i]
		
	res[0], res[-1] = post[1], pre[-2]
	for i in range(1, n-1):
		res[i] = pre[i-1] * post[i+1]
	return res
 
#time: o(n)
#memory: o(n)

review