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


  • 0
    J

    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;
        }
    };

Log in to reply
 

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