LintCode: Product of Array Exclude Itself

Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B WITHOUT divide operation.

Have you met this question in a real interview? 

Yes

Example

For A = [1, 2, 3], return [6, 3, 2].

Tags Expand 

Forward-Backward Traversal

Initial solution:
At the beginning, I try to get product of all elements and just divide the element itself to get the final array. However, if there is any zero in the original array, this solution doesn't work any more. Since the product will be 0, and we have to divide 0 which is impossible.

So I used two arrays to record left and right product of each element.
Time: O(n + n + n)
Space: O(2n)
Reference: http://algorithm.yuanbin.me/integer_array/product_of_array_exclude_itself.html

class Solution {
public:
    /**
     * @param A: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    vector<long long> productExcludeItself(vector<int> &nums) {
        // write your code here
        vector<long long> left;
        vector<long long> right;
        left.push_back(1);
        right.push_back(1);
        long long pro_left = 1;
        long long pro_right = 1;
        for(int i = 0; i < nums.size() - 1; i++){
            pro_left *= nums[i];
            pro_right *= nums[nums.size() - 1 - i];
            left.push_back(pro_left);
            right.push_back(pro_right);
        }
        vector<long long> result;
        for(int i =  0; i < nums.size(); i++){
            result.push_back(left[i] * right[nums.size() - 1 - i]);
        }
        return result;
    }
};

This problem can also be solved with O(1) space complexity.
We can store the left or right vector in the result vector, then use a variable to record right or left product and result at the same time.


Second Lintcode:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: /** * @param A: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { // write your code here vector<long long> res(nums.size()); vector<long long> left(nums.size(), 1); vector<long long> right(nums.size(), 1); long long leftproduct = 1; long long rightproduct = 1; for(int i = 0; i < nums.size() - 1; i++){ leftproduct *= nums[i]; left[i + 1] = leftproduct; } for(int j = nums.size() - 1; j > 0; j--){ rightproduct *= nums[j]; right[j - 1] = rightproduct; } for(int i = 0; i < nums.size(); i++){ res[i] = left[i] * right[i]; } return res; } };