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

### 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

**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
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.