- DS: Associative Array , Technique: Preprocessing

Time Complexity: O(n)

Space Complexity: O(N)

```
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size(), product = 1;
vector<int> prefix, suffix(len), output(len);
// vector<int> prefix and vector<int> prefx(len);
for (int i = 0; i < len; i++) {
product *= nums[i];
prefix.push_back(product);
}
product = 1;
for (int i = len - 1; i >= 0; i--) {
product *= nums[i];
suffix[i] = product;
}
output[0] = suffix[1];
output[len - 1] = prefix[len - 2];
for (int i = 1; i < len - 1; i++) {
output[i] = prefix[i - 1] * suffix[i + 1];
}
return output;
}
```

This is a straightforward approach, we can easily see that output[i] = prefix[i -1] * suffix[i + 1] ( 0 < i < last)

Note 1： Declare vector<int> prefix(len) and prefix.push_back()

2.Optimization

Follow-up requires Space Complexity should be O(1), so we should improve from S:O(N) to S: O(1)

This type of Improvement happens a lot in DP , etc fibonacci.It is still based on DP technique.we can use variables to bookkeeping instead of array . However in this problem, we can't. So we may need other techniques

Another optimization is to focus on time complexity O(1). We can do two scans on output array . That means we don't have to calculate a correct value of output[i] immdiately when we first get to that index, which is what we do in the first approach. However i was not able to get an clever observation . Below links give

https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space

One reason I could not figure it out is because I forgot one important property of product.: 1 times N = N;

Note: time complexity O(1), we can run two scans on a set.