Product of array except self

This post is a short explanation of an interesting leetcode problem I worked through this past week

Short description of problem

Input is an array of numbers
Output is an array where each index contains the product of all values except self
You can't use division
Should run in O(n) time

Example

Input = [1,2,3,4]
Answer = [24,12,8,6]

So for index[1] ( value 2)
You would do 1 * 3 * 4 = 12

Should run in O(n) time

This disqualifies the brute force O(N^2) solution
Where you loop through the array once for every value

#assumes no duplicates
res = []
for num in nums:
	count = 1
	for otherNum in nums:
		if num == otherNum:
			continue
		count*= otherNum
	res.append(count)
return res

Smart solution

The way to solve this is to reframe the problem.

Initially I framed the solution as
"return product of values except the current one"
A different way to say it is
"return product of values left of current * product of values right of current"

Implementation

Start by generating two arrays

leftProducts, which contains the product of all values left of index
rightProducts, which contains the product of all values right of index
Loop through input, and for each index, return leftProducts[i] * rightProducts[i]

Generating leftProducts

Initialize array to the length of nums
Set the first value to 1, this is done because there are no values to the left of the first value
Go through all nums starting from index 1,
set leftProducts[i] = leftProducts[i-1] * nums[i-1]

leftProducts = [0] * len(nums)
leftProducts[0] = 1 
for i in range(1,len(nums)):
	leftProducts[i] = leftProducts[i-1] * nums[i-1]

Visually it would look something like this for the first two iterations

Left Product

Generating rightProducts

Initialize array to the length of nums
Set the last value to 1, this is done because there are no values to the right of the first value
Go through all nums backwards starting from second to last index
set rightProducts[i] = rightProducts[i+1] * nums[i+1]

rightProducts = [0] * len(nums)
rightProducts[len(nums)-1] = 1

for i in range(len(nums)-2,-1,-1):
    rightProducts[i] = rightProducts[i+1] * nums[i+1]

Visually this would look something like Right Products

Producing the result

When you have performed these two steps the arrays should look like leftProducts = [1, 1, 2, 6]
rightProducts = [24, 12, 4, 1]

Now all you have to do is add them up

res = []
for i in range(len(nums)):
    res.append(leftProducts[i] * rightProducts[i])

And here's how that would look Answer And thats all there is to it!
As with most problems it usually helps a lot to draw the example and walk through it by hand.

If my descriptions aren't doing it for you I recommend this video which helped me understand the solution better.

Vik

Vik