10.Product of Array Except Self

Example
Input:  [1,2,3,4]
Output: [24,12,8,6]

Solution I : (Using Extra Space)

1. Create two array prefix and suffix of length n, i.e length of the original array, initilize prefix[0] = 1 and suffix[n-1] = 1 and also another array to store the product.

2. Traverse the array from second index to end.

3. For every index i update prefix[i] as prefix[i] = prefix[i-1] * array[i-1], i.e store the product upto i-1 index from the start of array.

4. Traverse the array from second last index to start.

5. For every index i update suffix[i] as suffix[i] = suffix[i+1] * array[i+1], i.e store the product upto i+1 index from the end of array

6. Traverse the array from start to end.

7. For every index i the output will be prefix[i] * suffix[i], the product of the array element except that element.

class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {

        int n = nums.size();
        vector<int> v;
        vector<int> pre(n);
        vector<int> suf(n);
        pre[0] = 1;
        suf[n - 1] = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            pre[i] = pre[i - 1] * nums[i - 1];
        }

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

        for (int i = 0; i < n; i++)
        {
            v.push_back(suf[i] * pre[i]);
        }
        return v;
    }
};