# C++ solution O(2N) time and O(1) space with explanation

• ``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int size = nums.size();
vector<int> result(size, 1);
// upper triangle
for (int i = 1; i < size; i++)
{
result[i] = nums[i - 1] * result[i - 1];
}

int product = 1;
// lower triangle
for (int i = size - 2; i >= 0; i--)
{
product *= nums[i + 1];
result[i] *= product;
}
return result;
}
};
``````
1. Imagine calculating the product of each column of a matrix without the diagonal element
1. Calculate upper triangle and lower triangle to get the answer

• Calculate upper triangle and lower triangle to get the answer

Those triangles are Θ(n2) large...

• Yes, but you only have to use a for loop to calculate all the elements.
For example: (upper triangle)
If numbers array nums = { 1, 2, 3, 4, 5 }

1. Declare a vector v = { 1, 1, 1, 1, 1 }
2. for i = 1 to 4
3. v[i] = v[i - 1] * nums[i - 1]
v[1] = v[0] * nums[0], v = { 1, 1, 1, 1, 1 }
v[2] = v[1] * nums[1], v = { 1, 1, 2, 1, 1 }
v[3] = v[2] * nums[2], v = { 1, 1, 2, 6, 1 }
v[4] = v[3] * nums[3], v = { 1, 1, 2, 6, 24 }
4. Already get the upper triangle result by O(N) time

• What is that v? The top row of the triangle? The rightmost column? What about the rest of the triangle? And where is the matrix? I only see your nums vector.

I really don't think your triangle analogy is working unless you explain how it's a special case and what you actually mean.

• The matrix is just for explanation.
If the numbers vector is { a0, a1, a2 }, the result vector is
v[0] = 1 * a1 * a2
v[1] = a0 * 1 * a2
v[2] = a0 * a1 * 1
I can declare an integer temp to store the result.
For upper triangle,

1. temp = 1
2. temp = temp * a1 = a1
3. temp = temp * a2 = a1 * a2
For lower triangle,
4. temp = 1
5. temp = temp * a1 = a1
6. temp = temp * a0 = a0 * a1

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