6. Product of Array Except Self

#leetcode/238

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.

Solution

Solution in C++ using brute force

The simplest method that comes to mind is, we can loop through the complete array using a pointer, sayย j, for every indexย i, and multiply all the elements at indexย jย except whenย i == j. This would ensure that we skip the element at indexย iย from being multiplied.

vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for(int i = 0; i < n; i++) {
            ans[i] = 1;
            for(int j = 0; j < n; j++) {
                if(i != j)
                    ans[i] *= nums[j];
            }
        }
        return ans;
    }

Solution in C++ using the division operation

What we would do is, we would find the product of all the numbers of our array and then divide the product with each element of the array to get the new element for that position in our final answer array. The problem going with this method is when we have aย 0ย in our array. In fact, we can't perform a division byย 0, as a result, we won't be able to get corresponding values in our final answer array for the indices havingย 0ย in our initial array at that position.
However, we can fix this problem by keeping the count of zeros in the array.

  1. If the count of zeros is 0 there are no problem, we just need to divide the product of array with every element.
  2. If the count of zeros is greater than 1, the array will be empty.
  3. If the count of zeros is 1, we need to find the index of the zero and the product of the array without the zero. Then we just place the product at the index of the zero and we are done.
vector<int> productExceptSelf(vector<int>& nums) {
	int n = nums.size();
	vector<int> ans(n, 0);
	int zeroCount = 0;
	int prod = 1;

	for(int num : nums) {
		if(num != 0)
			prod *= num;
		else if(++zeroCount == 2)
			return ans; 
	}
	for(int i = 0; i < n; i++) {
		if(zeroCount == 1)
			ans[i] = nums[i] != 0 ? 0 : prod;
		else
			ans[i] = prod / nums[i];
	}
	return ans;
}

Solution in C++ using Prefix Product and Suffix Product tecnique

Here's a smart idea. We can calculate lefts product and rights product of every element in 2 loops. Finally, we multiply them and we push the result in the result array. For example:

Numbers:       2      3      4       5
Lefts:         1      2    2*3   2*3*4
Rights:    3*4*5    4*5      5       1
Output:  1*3*4*5  2*4*5  2*3*5 1*2*3*4

If we allocate an array for lefts product and one for rights product, the space complexity would be O(n). To make it O(1), we just need to store lefts product and rights product in two variables.

vector<int> productExceptSelf(vector<int>& nums) {
	int n = nums.size();
	vector<int> ans(n, 0);
	int left = ans[0] = 1;
	int right = ans[n - 1] = 1;

	//calculate left product for every element
	for(int i = 1; i < n; i++) {
		left *= nums[i - 1];
		ans[i] = left;
	}

	//calculate right product for every element and multiply with left product
	for(int i = n - 2; i >= 0; i--) {
		right *= nums[i + 1];
		ans[i] *= right;
	}

	return ans;
}