Leetcode Study Day 8

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

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

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
 

Constraints:

2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

My solution

I actually use division operation to solve this question. But this is the first idea that come up to my head, so I record it here:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int tot_prod = 1;
        // To count how many zero are there in the array
        int zero_num = 0;
        for (int i = 0; i < n; i++){
            if (nums[i] == 0){
                zero_num ++;
                continue;
            }
            // Calculate the total product for all the elements
            tot_prod *= nums[i];
        }
        vector <int> answer;
        // If there is no zero
        if (zero_num == 0){
            for (int i = 0; i < n; i++){
                // each element in the answer is total product divided by itself
                answer.push_back(tot_prod / nums[i]);
            }
        }
        else if (zero_num == 1){
            // If there is one 0, all the element is 0 except for the index of 0
            for (int i = 0; i < n; i++){
                if (nums[i] == 0)
                    answer.push_back(tot_prod);
                else answer.push_back(0);
            }
        }
        else{
            // If there are more than one 0, all the elements are 0.
            for (int i = 0; i < n; i++){
                answer.push_back(0);
            }
        }
        return answer;
    }
};

Improved Solution

The improved idea is based on computing the products to the left and right of the current element and multiplying them, we obtain the product of all elements except the current one. To be specific, we firstly compute the product of all elements to the left of the current element.

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

Then we initiate a variabe right which is equal to 1 to represent the element at the right of the end element. Then we iterate the array from the end to the beginning, and update the answer array. The variable right is the product of all the elements to the right of the current element.

int right = 1;
for (int i = n - 1; i >= 0; i--){
    answer[i] = right * answer[i];
    right = right * nums[i];
}

Full code

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