# A REAL space O(1) method, even with O(n^2) time. The method is AC.

• The statement is misleading. If use return result to act as a bridge. It is not a O(1) space.
Every item has a product of (n-1) multiplication， there are n*(n-1) in place multiplication in total. That's O(n^2) time complexity.
For time-space trade-off. It have to use extra O(n) space to store middle products.
My method just return the input array nums as result, it's O(1) in space, but O(n^2) in time.

``````class Solution {
public:
long helper(vector<int> &nums, int left, int right)
{
long ret, lp, rp;
if(left +1 == right)
{
swap(nums[left], nums[right]);
ret = nums[left]*nums[right];
return ret;
}else if(left == right)
{
ret = nums[left];
nums[left]=1;
return ret;
}
int mid = left + (right-left)/2;
lp = helper(nums, left, mid);
rp = helper(nums, mid+1, right);
for(int i = left; i <= mid; i++)
{
nums[i] *= rp;
}
for(int i = mid+1; i <= right; i++)
{
nums[i] *= lp;
}
return lp*rp;
}

vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
long ret;
ret = helper(nums, 0, len-1);

return nums;
}
};``````

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