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

  • 0

    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 {
        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];
                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;

Log in to reply

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