238. Product of Array Except Self

Hint

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize a vector to store the products of elements to the left of each index
        // Initialize a vector to store the products of elements to the right of each index
        // Initialize a vector to store the final result

        // Compute the products of all elements to the left of each index
        for ()
        {
            // Each element in arr1[i+1] is the product of all elements before nums[i+1]
        }

        // Compute the products of all elements to the right of each index
        for ()
        {
            // Each element in arr2[i-1] is the product of all elements after nums[i-1]
        }

        // Compute the final result by multiplying the corresponding elements of arr1 and arr2
        for ()
        {
            // The product of all elements except nums[i] is arr1[i] * arr2[i]
        }
        // Return the result vector
    }
};

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)$

Hint - Space Improved

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        // Initialize the result array with 1s, as we will be using multiplication.

        // First pass: calculate the product of all elements to the left of each index.
        for ()
        {
            // res[i] will be the product of all elements to the left of i.
        }

        // Variable to store the product of all elements to the right of the current index.
        // Second pass: calculate the product of all elements to the right of each index and
        // multiply it with the product from the first pass.
        for ()
        {
            // Multiply with the product of elements to the right.
            // Update the right product for the next iteration (one index to the left).
        }
    }
};

• 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)$