[Algorithms] 9 - Product of Array Except Self

Link for the problem

Link for the solution

Overview

To solve the problem is pretty easy. But the given conditions are what make this problem very tricky. I would like to introduce the problem because the solution is pretty unique.

Problem in detail

The constraints for this problem are:

• Time complexity: O(n)
• Space complexity: O(1)
• Cannot use division

Notice that the problem will not count the returning array as an extra space.

It seems almost impossible to solve the problem with those constraints. Especially achieving O(1) space complexity without using division drove me crazy to think about the solution. So I gave it up and looked at the solution.

Solution

The solution was something that I have never seen, but easy to understand. First, we need to think how to get the products without itself. It is actually the product of left side of an element and the right side of an element.

[ 1, 2, 3, 4 ]

ex) product without 1

- left side: 1 (does not exist)
- right side: 2*3*4 (without 1)
- left side * right side = 1 * 24 = 24


ex) product without 3

- left side: 1*2 (does not exist)
- right side: 4 (without 3)
- left side * right side = 1 * 2 * 4 = 8

Next, we need to find the way to get prefixes and postfixes in a linear time, and using only constant space. Actually this part is very hard to come up with by ourselves.

The way to create prefixes is:

1. Set up a variable prefix, initialized with 1.
2. Push the prefix to the returning array.
3. Keep multiplying prefix as loop goes through.

Notice that the first prefix is always going to be 1 since there is no element on the left side of the first element.

After the step, we will get an array that filled with prefixes for each element. Now all we need to do is get postfixes for each element and simply update the returning array by multiplying those postfixes.

Code implementation

    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res;
        int prefix = 1;
        for (int i = 0; i < nums.size(); i++)
        {
            res.push_back(prefix);
            prefix *= nums[i];
        }
        int postfix = 1;
        for (int i = nums.size()-1; i >= 0; i--)
        {
            res[i] *= postfix;
            postfix *= nums[i];
        }
        return res;
    }