Two clean best solutions one using O(n) space the other only O(1) space in C++


  • 2
    class Solution {
    public:
        //normal method using linear space;
        vector<int> productExceptSelf(vector<int>& nums) 
        {
            if(nums.empty()) return vector<int>();
            int size = nums.size();
            int lProducts[size], rProducts[size];
            lProducts[0] = 1, rProducts[size-1] = 1;
            for(int i = 1; i < size; ++i)
            {
                lProducts[i] = nums[i-1]*lProducts[i-1];
                rProducts[size-i-1] = nums[size-i]*rProducts[size-i];
            }
            vector<int> v(size);
            for(int i = 0; i < size; ++i)  
                v[i] = lProducts[i]*rProducts[i];
            return v;
        }
    	
        //actually we can do it with constant extra space;
    	vector<int> productExceptSelf(vector<int>& nums) 
        {
            if(nums.empty()) return vector<int>();
            int size = nums.size(), t = 1;
            vector<int> v(size);
            v[0] = 1;
            for(int i = 1; i < size; ++i) v[i] = v[i-1]*nums[i-1];
            for(int i = size-2; i >= 0; --i)
                v[i] *= (t *= nums[i+1]);
            return v;
        }
    };

  • 0
    T
    This post is deleted!

Log in to reply
 

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