Leetcode:238.Product of Array Except Self

This question reminds me of an album titled "From Left to Right" by Bill Evans. The key insight is also from left to right, then from right to left.

When I first saw this problem, my intuitive approach was to compute the product of all elements; hence, nums[i] equals the product divided by nums[i].

But an obvious problem is if the nums[i] equals zero, the algorithm would crash.

In this situation, I wrote an algorithm whose core goal is not to be distracted by dividing by zero, and get the right ans[i] at the same time.

Thus, I observed what's going on when the array has zero. I noticed that when the array doesn't have zero, the algorithm works fine, when it contains exactly one zero, except that the nums[i] equals zero, the nums[i] will be the product of the array except nums[i], when it contains two or more zeros, all elements will be 0 in the end.

Here's the code:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int>ans(nums.size(),1);
       int zero=0;
       int pro=1;
       for(int i=0;i<nums.size();i++){
        if(nums[i]==0){
            zero++;
        }
       }
       if(zero>1){
        for(int k=0;k<nums.size();k++){
            nums[k]=0;
        }
       }
       else if(zero==1){
        int check;
        for(int j=0;j<nums.size();j++){
            if(nums[j]!=0){
                pro=pro*nums[j];
                ans[j]=0;
            }
            else{
                check=j;
            }
        }
        ans[check]=pro;
       }
       else{
        for(int h=0;h<nums.size();h++){
            pro=pro*nums[h];
        }
        for(int g=0;g<nums.size();g++){
            nums[g]=pro/nums[g];
        }
       }
       return nums;
    }
};

This works very well. By counting the number of zeros, I solved this in a simple way, and the time is O (N) and the space is O(1). The world became colorful when my submission was accepted.

But when I went back to re-read the description, the world's color became faint, because there was a sentence: ''You must write an algorithm that runs in O(n) time and without using the division operation.''

So I was forced to find a new way.

I just started a new observation, and I wrote down the array on paper. I noticed that if the array is [a,b,c,d], the answer would be [bcd,acd,abd,abc]; furthermore, I noticed that the answer equals [1*bcd,a*1*cd,ab*1*d,abc*1], equals [right*left,right*left,....], so the problem transformed to " how to know both left and right nums[i]'s product.'' !

So, I started to determine how to achieve both the left and right products.

My starting point is the left product. Use the same example [a,b,c,d], their left product, which is equal to [1,a,ab,abc]. Obviously, this tells us that just using a for loop, we can calculate the exact left product of every element.

The algorithm is like this:

vector<int>left_pro(nums.size(),1);
int left_product=1;
for(int i=0;i<nums.size();i++){
    left_pro[i]=left_product;
    left_product=left_product*nums[i];
  }

Furthermore, the for loop can be optimized like this:

for(int i=1;i<nums.size();i++){
    left_pro[i]=left_pro[i-1]*nums[i-1];
  }

How does this work? And why can it be optimized? Please look at the demonstration:

In the first algorithm, we have:

nums=[a,b,c,d];

And we want to get:

left_pro=[1,a,ab,abc];

How do we calculate each left product, and when should we assign it to left_pro[i]?

First, how do we calculate each left product?

I created left_product. As I read the nums[i], I multiply it with left_product. Because as I do this to every element from the left, left_product changes from 1 → 1*a → a*b → ab*c. Now we know how to calculate each left product.

It's like:

 left_product=left_product*nums[i];

Second, when should we assign left_pro[i]=left_product?

Back to the left_pro we want to get. the left_pro nums[0] equals 1, also equals the left_product which doesn't change yet. We know the assignment should be before the calculation. It seems like this:

for(int i=0;i<nums.size();i++){
    left_pro[i]=left_product;
    left_product=left_product*nums[i];
  }

(Extra question: Can the calculation come before the assignment? What would the algorithm look like? Try it yourself - the answer is shown below)

Now, we know how the for loop works. Why can it be optimized like that?

If we observe more details, we can discover that when the computer runs left_pro[i]=left_product, it actually runs as left_pro[i]=left_product(i-1)*nums[i-1], and in the case of i-1, we have left_pro[i-1]=left_product(i-1).

(i=2){
    left_pro[2]=left_product;
    left_product=left_product*nums[2];
}
(i=3){
    left_pro[3]=left_product
               =left_product*nums[2];
               =left_pro[2]*nums[2]

So we can combine it, then we get this:

left_pro[i]=left_pro[i-1]*nums[i-1];

Now, we know how the for loop helps us to get[1,a,ab,abc], now we need to get the right_pro, which is [bcd,cd,d,1]. Multiplying left_pro with right_pro, we get the final result[bcd,acd,abd,abc].

The algorithm is like this:

vector<int>right_pro(nums.size(),1);
int right_product=1;
for(int k=nums.size()-1;k>=0;k--){
    right_pro[k]=right_product;
    right_product=right_product*nums[k];
  }

The algorithm of left_pro is from left to right, and the algorithm of right_pro is from right to left. Also, it can be optimized like this:

right_pro[k]=right_pro[k+1]*nums[k+1];

because:

(k=3){
    right_pro[3]=right_product;
    right_product=right_pro[3]*nums[3];
}
(k=2){
    right_pro[2]=right_product
               =right_product*nums[3];
               =right_pro[3]*nums[3]

Then we get the final algorithm:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> ans(nums.size(),1);
    vector<int>left_pro(nums.size(),1);
    int left_product=1;
    for(int i=1;i<nums.size();i++){
    left_pro[i]=nums[i-1]*left_pro[i-1];
  }// left product calculation
    vector<int>right_pro(nums.size(),1);
    int right_product=1;
    for(int k=nums.size()-2;k>=0;k--){
    right_pro[k]=right_pro[k+1]*nums[k+1];
  }//right product calculation
    for(int j=0;j<nums.size();j++){
        ans[j]=left_pro[j]*right_pro[j];
    }//final product calculation

    return ans;
}
};

The time is O(n). The space is O(n).

At this point, you can submit it and appreciate the colorful world, but we go back to description again, there is another sentence: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

But we're not the type to give up easily, are we? Let's find where to optimize.

The description demands that the approach should be written in O(1), meaning we can only allocate the answer array.

First, we noticed that the output didn't demand that we return arrays of left_product and right_product, so we can replace the left_product with ans. It seems like:

 for(int i=1;i<nums.size();i++){
        ans[i]=nums[i-1]*ans[i-1];
}

This makes the left_pro array unnecessary. But what about right_pro?

Let's go back to the basics. Now we have:

nums=[a,b,c,d]
left_pro=[1,a,ab,abc]

In the previous algorithm(which passed the tests), we still needed to calculate the right_pro. Put differently, we don't need to store every element in the right_pro; in other words, when calculating the right_pro, multiplying right_pro with ans(equals left_pro), we end up with an O(1) space algorithm!

It seems like:

 int right_product=1;
 for(int k=nums.size()-1;k>=0;k--){
        ans[k]=ans[k]*right_product;
        right_product=right_product*nums[k];
}

First, we need to multiply ans[k] with right_product, which means multiplying left_product by right_product. So we get this:

ans[k]=ans[k]*right_product;

Second, we need to calculate what the right_product is. So we get this:

right_product=right_product*nums[k];

Combining it with the left_product calculation, we get:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> ans(nums.size(),1);
    for(int i=1;i<nums.size();i++){
        ans[i]=nums[i-1]*ans[i-1];
    } 
    int right_product=1;
    for(int k=nums.size()-1;k>=0;k--){
        ans[k]*=right_product;
        right_product*=nums[k];
}
    return ans;
}
};

The time is O(n), and the space is O(1); we got a great algorithm.

If you'd like to go listen to the album "From Left to Right", the code sounds better with Bill Evans.

Thanks for reading.

extra question's answer:

for(int i=1;i<nums.size();i++){
    left_product=left_product*nums[i];
    left_pro[i]=left_product;
  }