The Solution of "Product of Array Except Self" under my thinking

This post is just my thinking of the solution for the famous coding problem which is a problem #238 posted in Leetcode in which you can refer from here.

I will asume that you all have read and understood the requirement of this problem so I would not repeat it in this post.

Actually I write this post to enhance my skill of solving problems using my non-native language in writing (of course no marketing intended). So please forgive me if you may see this post without satisfaction or I will somehow show my weak explanation or mistakes. Much appreciation if you give some feedbacks to this post so that I can make this post better.

To think of this solution quickly, it is more likely to think of the nested loops which can easily solve the problem with O(n^2) in terms of time complexity. But if you are in an interview session and you are asked to solve this problem. A solution like nested loops for this problem is not usually appreciated. Another better solution that I just have thought after researching prefix sum (I studied it again) . This will be my beginning of the post. For example, this will be an input: [1, 2, 3, 4] and the output should be [24, 12, 8, 6]. Look at the input, how can I handle to have the expected output? Now it's time to adopt the prefix sum approach. But prefix sum would not work here, we should use "prefix product" (I named it) .

So to use prefix product, aka accumulative product, I would introduce a new variable whose length is as same as the size of the input array. After handling the prefix product, the solution is 50% achieved. You can handle the prefix product by watching the steps and the implementation below.

Introduce the output array variable out with the size is similiar to the one which is of the input array.
Initialize the out variable with value 1 so that we can easily accumulate the sequential product.
Make a loop to finally get a prefix product of the input array.

int[] out = new int[inp.Length];
out[0] = 1;
for (int i = 1; i < inp.Length; i++) {
    out[i] = out[i-1] * inp[i-1];
}

In the above implementation, you can figure out the big O notation in terms of time complexity and space complexity are both O(n) (n is the size of the input array). So that's it, O(n) is taken just to have a prefix product.

Now this will be the most difficult part which requires us to stay more focus. Only by doing some observation after having a prefix product can we realize a rule. When you know this rule, you have the key weapon to finalize this problem.

out[i] = a[0]. ... .a[i-1]
out[n-1] = a[0]. ... .a[n-2] (n is a size of the input array)
out[n-x] = a[0]. ... .a[n-x-1] (x is always smaller than n and greater than 1)

But do you realize that out[n-x] is missing its product from a range of inp[n-x+1] to inp[n-1]???

How can we solve that miss? Do we need something like a multiplier? A key is here, only by forming a multiplier which is the product from a range of inp[n-x+1] to inp[n-1] can we realize that we solved this problem.

The rest of the implementation is here:

Make a reverse loop to form a multiplier and use it to multiple with the item which is missing its product result within a prefix product array.

int multiplier = 1;
for (int i = inp.Length - 1; i >= 0; i--) {
    out[i] = out[i] * multiplier;
    multiplier = multiplier * inp[i];
}

Again this would cost O(n) in terms of time complexity.

So in general, it takes only O(n) to solve this problem in terms of time complexity and space complexity. On the contradict, the brute force one would cost O(n^2).

Mục lục