Let’s say the array is {a_1, a_2, …, a_n}. For each element in the array, say a_i, we want to find a_1*a_2*...*a_i-1*a_i+1*a_i+2*...*a_n. Let’s define the left product of a_i to be the product of all elements which are on the left of a_i. So lp_i (left product of a_i) = a_1*a_2*...*a_i-1. Similarly define right product of a_i to be the product of all elements which are on the right of a_i. So rp_i (right product of a_i) = a_i+1*a_i+2*...*a_n.
You can notice that essentially for each element a_i we have to find lp_i*rp_i. Traversing from the last element to the first element, we can easily find right product for each element in linear time. Then, we can traverse from left to right and keep track of the left product for each element and multiply it with the right product.
Instead of using an extra array for the right product, we store the right product in the array which we want to return thus saving space.
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans(nums.size(), 1);
for (int i=nums.size()-2; i>=0; i--)
ans[i] *= ans[i+1]*nums[i+1];
int partialProd = 1;
for (int i=1; i<nums.size(); i++) {
partialProd *= nums[i-1];
ans[i] *= partialProd;
}
return ans;
}
Time complexity: O(n)
Space complexity: O(1) except output array. O(n) including output array.