problem:

<aside>

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

ex.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

</aside>

solution:

<aside>

• keep an output array → array of 1’s length n
• run 2 passes on nums
• 1st pass → populate output array with prefix products at each index
• 2nd pass → traverse from the end and multiply the prefixes with the suffix product at each index - use a separate variable to maintain suffix product through each iteration

ex. nums = [1,2,3,4], output = [1,1,1,1]

1st pass: output = [ 1, 11, 12, 2*3] = [1,1,2,6]

2nd pass: output = [ 212, 34, 2*4, 6] = [24,12,8,6]

code:

def productExceptSelf(nums):
		n = len(nums)
		output = [1]*n
		
		for i in range(1, n):
				output[i] = output[i-1]*nums[i-1]
				
		suffix_product = 1
		for i in range(n-2, -1, -1):
				suffix_product *= nums[i+1]
				output[i] *= suffix_product
		
		return output

complexity:

<aside>

2 * O(n) → O(n) time

O(n) space → created output array of length n

</aside>

walkthrough:

<aside>

input: nums = [-1,1,0,-3,3] , output = [1,1,1,1,1]

output 1st pass:

output 2nd pass:

output: [0, 0, 9, 0, 0]

</aside>