# Associative Array + Preprocessing

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.