Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4] Output: [24,12,8,6] Note: Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
// 40ms, 80%
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
const int N = nums.size();
// res[i] is product to the left of it (exclusive of i)
vector<int> res(N);
res[0] = 1;
for (int i = 1; i < N; i++) {
res[i] = res[i-1] * nums[i-1];
}
int R = 1;
for (int i = N-1; i >= 0; i--) {
res[i] *= R;
R *= nums[i];
}
return res;
}
};
// 44ms, 38%
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> L(nums.size()), R(nums.size());
int ls = 1, rs = 1;
const int N = nums.size();
for (int i = 0; i < N; i++) {
ls *= nums[i];
rs *= nums[N - 1 - i];
L[i] = ls;
R[N - 1 - i] = rs;
}
vector<int> res(N);
res[0] = R[1];
res[N-1] = L[N-2];
for (int i = 1; i < N-1; i++) {
res[i] = L[i-1]*R[i+1];
}
return res;
}
};