LeetCode Q238: Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

Two passes, forward and backward.

	class Solution {
	public:
	vector<int> productExceptSelf(vector<int>& nums) {
	vector<int> res(nums.size(), 1);
	if(nums.size()==0)
	return nums;
	for(int i=1; i<nums.size(); i++)
	res[i] = res[i-1]*nums[i-1];
	int tmp1=nums[nums.size()-1];
	nums[nums.size()-1]=1;
	for(int i=nums.size()-2; i>=0; i--){
	int tmp2 = nums[i];
	nums[i] = tmp1*nums[i+1];
	tmp1 = tmp2;
	}
	for(int i=0; i<nums.size(); i++)
	res[i]=res[i]*nums[i];
	return res;
	}
	};

view raw Q238ProductOfArrayExceptSelf.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	vector<int> productExceptSelf(vector<int>& nums) {
	vector<int> res=nums;
	if(nums.empty())
	return res;
	for(int i=0; i<nums.size(); i++)
	nums[i] = i==0? nums[i]:nums[i-1]*nums[i];
	for(int i=nums.size()-1; i>=0; i--)
	res[i] = i==res.size()-1? res[i]:res[i]*res[i+1];
	for(int i=0; i<res.size(); i++){
	if(i==0)
	res[i] = 1*res[i+1];
	else if(i==res.size()-1)
	res[i] = nums[i-1]*1;
	else
	res[i] = nums[i-1]*res[i+1];
	}
	return res;
	}
	};

view raw Q238Rnd2.cpp hosted with ❤ by GitHub