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;
}