# Daily Coding Problem Write-up

## Day 2— Product of Array Except Self

Given an array `nums`

of n integers where n > 1, return an array `output`

such that `output[i]`

is equal to the product of all the elements of `nums`

except `nums[i]`

.

`O(n) runtime, O(n) space`

vector<int> productExceptSelf(vector<int>& nums) {

int n = nums.size(); // Initialize vectors (i.e. arrays) of n 1’s vector<int> result(n, 1);

vector<int> fromBegin(n, 1);

vector<int> fromEnd(n, 1); for(int i=1; i<n; i++){

fromBegin[i] = fromBegin[i-1] * nums[i-1];

fromEnd[i] = fromEnd[i-1] * nums[n-i];

}

for(int i=0; i<n; i++){

result[i] = fromBegin[i] * fromEnd[n-1-i];

}

return result;

}

**Explanation:**

Let’s take `nums = [1,2,3,4,5]`

as an example.

After the 1st pass,

`fromBegin = [1, 1x1, 2x1x1, 3x2x1x1, 4x3x2x1]`

`fromEnd = [1, 5x1, 4x5x1, 3x4x5x1, 2x3x4x5x1]`

Notice they are look like mirror images of one another, i.e. each array contains half the product needed. Therefore, in order to construct the result array, we have to combine the `fromBegin`

and `fromEnd`

arrays like so:

`result[i] = fromBegin[i] x fromEnd[n-1-i];`

More specifically,

`result[0] = fromBegin[0] x fromEnd[5–1–0] = (1) x (2x3x4x5x1) = 2x3x4x5 (i.e. product of all elements except 1)`

`result[1] = fromBegin[1] x fromEnd[5–1–1] = (1x1) x(3x4x5x1) = 1x3x4x5 (i.e. product of all elements except 2)`

`result[2] = fromBegin[2] x fromEnd[5–1–2] = (2x1x1) x(4x5x1) = 1x2x4x5 (i.e. product of all elements except 3)`

so on and so forth…

`O(n) runtime, O(1) space (if we don't count the output array)`

`vector<int> productExceptSelf(vector<int>& nums) {`

int n = nums.size();

vector<int> result(n, 1);

int fromBegin = 1;

int fromEnd = 1;

for(int i=1; i<n; i++){

fromBegin *= nums[i-1];

result[i] *= fromBegin;

fromEnd *= nums[n-i];

result[n-1-i] *= fromEnd;

}

result[0] = fromEnd;

result[n-1] = fromBegin;

return result;

}

**Space Optimization:**

If we look at how we calculated the `result`

array from `fromBegin`

and `fromEnd`

arrays, we'll find that each element in `fromBegin`

and `fromEnd`

were actually only used once. This means we don't have to store the intermediate values calculated in the `fromBegin`

and `fromEnd`

arrays.

More specifically, following the same example with `nums = [1,2,3,4,5]`

, we can first initialize `fromBegin`

and `fromEnd`

as 1, and result as `[1,1,1,1,1]`

, then:

In the first iteration,

`fromBegin = 1 x 1`

`fromEnd = 5 x 1`

At this instance, `fromBegin`

can already be multiplied into `result[1]`

and `fromEnd`

can already be multiplied into `result[5–1–1]`

.

In the second iteration,

`fromBegin = 1 x 1 x 2`

`fromEnd = 4 x 5 x 1`

At this instance, `fromBegin`

can already be multiplied into `result[2]`

and `fromEnd`

can already be multiplied into `result[5–1–2]`

.

After the first pass, all values in result are ready except the first and the last ones. Right now,

`fromBegin = 1 x 1 x 2 x 3 x 4`

`fromEnd = 2 x 3 x 4 x 5 x 1`

Meaning `fromBegin`

is exactly the value of `result[4]`

and `fromEnd`

is exactly the value of `result[0]`

! Therefore, we can simply do:

`result[0] = fromEnd;`

result[n-1] = fromBegin;

Note:

- This is one of those problems where you just have to stare at the problem long enough until you find the right pattern. Not fun.