238. Product of Array Except Self

Prompt

You must write an algorithm that runs in O(n) WITHOUT using the division operation.

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.

Examples

• Example 1:
  • Input: nums = [1,2,3,4]
  • Output: [24,12,8,6]
• Example 2:
  • Input: nums = [-1,1,0,-3,3]
  • Output: [0,0,9,0,0]

Solution

In C++

vector<int> productExceptSelf(vector<int>& nums) {
	vector<int32_t> prefix(nums.size());
	prefix[0] = 1;
	for (int i = 0; i < nums.size() - 1; i++) {
		prefix[i + 1] = prefix[i] * nums[i];
	}
	vector<int32_t> suffix(nums.size());
	suffix[nums.size() - 1] = 1;
	for (int i = nums.size() - 2; i >= 0; i--) {
		suffix[i] = suffix[i + 1] * nums[i + 1];
	}
 
	vector<int32_t> answer(nums.size());
	for (int i = 0; i < nums.size(); ++i) {
		answer[i] = prefix[i] * suffix[i];
	}
	return answer;
}

Explanation

The idea for this one is that we create prefix and suffix product arrays. For any given index, prefix has the product of all the elements in the input array to the left of that index. Similarly, suffix does the same thing, but to the right. For indices on the edge of the array, the product of the “elements” outside the array is 1, because it makes the math generic.

Big O Analysis

Time Complexity

The time complexity is $O(n)$.

Auxiliary Space Complexity

The space complexity is $O(n)$.