Description

Prefix/postfix, is an array trick to track partial summation/addition answers.
?

Reach for when

Runtime

O(n)

Visualization

Pseudocode

prefix=[basecase]
for item in items:
	prefix.push(update(prefix[-1]))
return prefix

Code

def product_except_self(nums):
	n = len(nums)

	# prefix[i] = product of everything to the LEFT of i
	prefix = [1] * n
	for i in range(1, n):
		prefix[i] = prefix[i - 1] * nums[i - 1]

	# postfix[i] = product of everything to the RIGHT of i
	postfix = [1] * n
	for i in range(n - 2, -1, -1):
		postfix[i] = postfix[i + 1] * nums[i + 1]

	# answer[i] = everything left of i * everything right of i
	answer = [1] * n
	for i in range(n):
		answer[i] = prefix[i] * postfix[i]

	return answer