Product of Array except self

You are given an array containing n integers (n>1), you need to return an output array such that output [i] is equal to the product of all the elements of the array except the i’th element.

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

Constraint: You need to solve the problem without using division operator and in O(n) time complexity.

Algorithm:

1. Build two arrays left and right of the same size as that of the input array. Initialize left [0] with array [0] and right [n-1] with array [n-1].
2. Loop for i = 1 to (n-1), and in each iteration set left [i] = array [i] * left [i-1]. This means that left [i] contains the product of all elements to the left of i’th element in the array alongwith the current element.
3. Loop for i = (n-2) to 0, and in each iteration set right [i] = right [i+1] * array [i]. This means that right [i] contains the product of all elements to the right of i’th element in the array alongwith the current element.
4. Now, create another vector output of the same size. Loop for i = 0 to (n-1), and in each iteration, do the following.
   If i = 0, set output [i] = right [i+1] {product if all elements to the right of 0’th element}. If i = (n-1), set output [i] = left [i-1] {product of all elements to the left of (n-1)’th element}. For all other values of i, set output [i] = right [i+1] * left [i-1].

For a better understanding, look at the code below.

#include <bits/stdc++.h>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n=nums.size();
    vector<int> left(n);
    vector<int> right(n);
    left[0] = nums[0];
    right[n-1] = nums[n-1];
    for(int i=1; i<left.size(); i++){
        left[i] = nums[i]*left[i-1];
    }
    for(int i = n-2; i>=0; i--){
        right[i] = nums[i]*right[i+1];
    }
    vector<int> res(n);
    for(int i=0; i<nums.size(); i++){
        if(i==0){
            res[i] = right[i+1];
        }else if(i==nums.size()-1){
            res[i] = left[i-1];
        }else{
            res[i] = right[i+1]*left[i-1];
        }
    }
    return res;
}

int main(){
	vector <int> nums = {1, 2, 3, 4};
	vector <int> output = productExceptSelf(nums);
	for(auto i:output){
		cout<<i<<" ";
	}
	return 0;
}

Also, check out another popular interview problem Find pivot index.