## Product of Array Except Self

Given an array of

*n*integers where*n*> 1,`nums`

, return an array `output`

such that `output[i]`

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

except `nums[i]`

.
Solve it without division and in O(

*n*).
For example, given

`[1,2,3,4]`

, return `[24,12,8,6]`

.
Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

### Analysis:

This question has three requirements:

- no division
- O(n) time complexity
- O(1) space complexity

First let's only consider the time complexity O(n).

What can be done within O(n) time?

- Scan the whole array once (often from the start to the end).

What about scan the array again?

- Yes. It is still O(n) time ( \(O(2n) = O(n)\) ).

- No. It is \(O(n*n)=O(n^2)\)

From the question above, we know that, at least we could scan the array twice (or other countable number if needed.).

OK, let's scan the array from start to end, e.g., [1,2,3,4].

The accumulated products can then be saved:

*P_forward = [1,1*2, 1*2*3, 1*2*3*4] = [1, 2, 6, 24]*Let's get back to the problem, we need to get the product of all nums without current position, intuitively:

nums = [1, 2, 3, 4], for position 2 where nums[2] = 3, the product we want to have can be viewed:

- left = 1*2
- right = 4
- p = left * right

We already have the accumulated product from our first scanning, P_forward = [1, 2, 6, 24], which means, P_forward[i] = product from 0 to i. What about the product from i+1 to end?

*The*

*backward*

*product is computed by scanning the array*

**backward:**

**P_backward = [4, 12, 24, 24]***Note that, these products include the current element, so by adding a "1" in front of the product arrays will do fine:*

**P_forward = [1, 1, 2, 6, 24]**

**P_backward = [1, 4, 12, 24, 24]**

**then, the final results can be easily computed:**

res[0] = P_forward[0] * P_backward[3] = 24 (product before [0] * product from last to [1])

res[1] = P_forward[1] * P_backward[2] = 12 (product before [1] * product from last to [2])

res[2] = P_forward[2] * P_backward[1] = 8

res[3] = P_forward[3] * P_backward[0] = 6

res = [24, 12, 8, 6]

Now the problem is solved but:

- O(1) space complexity

- P_forward can be stored in the output array
- P_backward is actually not necessary, each time we compute one value, multiply it to correct P_forward, then the P_backward value can be overwritten for the next computation.

### Code(C++):

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { vector<int> res(1,1); for (int i=0;i<nums.size();i++){ res.push_back(res.back()*nums[i]); } int b = 1; for (int i=0;i<nums.size();i++){ res[nums.size()-i-1] = res[nums.size()-i-1] * b; b = b* nums[nums.size()-i-1]; } res.pop_back(); return res; } };

### Code(Python):

class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ res = [1] for num in nums: res.append(res[-1]*num) b = 1 for i in range(len(nums)): res[len(nums)-i-1] = res[len(nums)-i-1] * b b = b* nums[len(nums)-i-1] return res[0:-1]

## No comments:

## Post a Comment