238. Product of Array Except Self

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        vector<int> res(n);

        for (int i = 0; i < n - 1; ++i)
        {
            left[i + 1] = left[i] * nums[i];
        }

        for (int i = n - 1; i > 0; --i)
        {
            right[i - 1] = right[i] * nums[i];
        }

        for (int i = 0; i < n; ++i)
        {
            res[i] = left[i] * right[i];
        }
        return res;
    }
};

• T: $O(N)$
• S: $O(N)$

Space Improved

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> res(n, 1);

        for (int i = 1; i < n; ++i)
        {
            res[i] = nums[i - 1] * res[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; --i)
        {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};

• T: $O(N)$
• S: $O(1)$