Description
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Solution
All the problem comes with this constraint :(
without using the division operation.
For answer[i] and nums of length n, answer[i] = (nums[i] * nums[i+1] * ... * nums[i-1]) * (nums[i+1] * ... * nums[n-1]). Therefore, we could construct two partial sum array prefix and suffix, where prefix[i] = nums[i] * prefix[i-1] and suffix[i] = nums[i] * suffix[i+1].
By using the prefix and suffix array, answer[i] would be prefix[i-1] * suffix[i+1].
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
size_t n = nums.size();
vector<int> prefix(nums), suffix(nums), output(n);
partial_sum(prefix.begin(), prefix.end(), prefix.begin(), multiplies<int>());
partial_sum(suffix.rbegin(), suffix.rend(), suffix.rbegin(), multiplies<int>());
for (auto i = 0; i < n; i++) {
int pre_sum = i? prefix[i-1]: 1;
int suf_sum = i == n-1? 1: suffix[i+1];
output[i] = pre_sum * suf_sum;
}
return output;
}
};
Didn’t noticed there exist a std::partial_sum to construct the two prefix sum array until seeing a solution on Leetcode. cppreference
The time complexity of the above implementation is $O(n)$ and space complexity $O(n)$. We could further improve the it and make the space complexity to $O(1)$ by calculating prefix and suffix sum array on the fly:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
size_t n = nums.size();
vector<int> output(n, 1);
int prefix = 1, suffix = 1;
for (size_t i = 0; i < n; i++) {
output[i] *= prefix;
output[n-i-1] *= suffix;
prefix *= nums[i];
suffix *= nums[n-i-1];
}
return output;
}
};