# 238. Product of Array Except Self

## Description

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.

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

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]


Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

## Solutions

Solution 1: Two Passes

We define two variables $left$ and $right$, which represent the product of all elements to the left and right of the current element respectively. Initially, $left=1$, $right=1$. Define an answer array $ans$ of length $n$.

We first traverse the array from left to right, for the $i$th element we update $ans[i]$ with $left$, then $left$ multiplied by $nums[i]$.

Then, we traverse the array from right to left, for the $i$th element, we update $ans[i]$ to $ans[i] \times right$, then $right$ multiplied by $nums[i]$.

After the traversal, the array ans is the answer.

The time complexity is $O(n)$, where $n$ is the length of the array nums. Ignore the space consumption of the answer array, the space complexity is $O(1)$.

We can optimize the above method space complexity.

Since the final result is to be multiplied into the result res, it is not necessary to store the product in a separate array, but directly accumulate into the result res.

1. We traverse from the front first, and store the accumulation of the product in the result res
2. Then start traversing from the back, using a temporary variable right, initialized to 1
3. Then keep accumulating each time, and finally get the correct result
• class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (int i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
}

• class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
for (int i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (int i = n - 1, right = 1; ~i; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
};

• class Solution: # 2 extra arrays
def productExceptSelf(self, nums):
if nums is None or len(nums) == 0:
return nums

# Product from index=0 to index=i-1
from_left = [1] * len(nums)
for i in range(1, len(nums)):
from_left[i] = nums[i - 1] * from_left[i - 1]

# Product from index=n-1 to current position
from_right = [1] * len(nums)
for i in range(len(nums) - 2, -1, -1):
from_right[i] = nums[i + 1] * from_right[i + 1]

# Calculate result
result = [0] * len(nums)
for i in range(len(nums)):
result[i] = from_left[i] * from_right[i]

return result

############

class Solution: # follow up, no extra space
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
left = right = 1
for i, v in enumerate(nums):
ans[i] = left
left *= v
for i in range(n - 1, -1, -1):
ans[i] *= right
right *= nums[i]
return ans

############

class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
dp = [1] * len(nums)
for i in range(1, len(nums)):
dp[i] = dp[i - 1] * nums[i - 1]
prod = 1
for i in reversed(range(0, len(nums))):
dp[i] = dp[i] * prod
prod *= nums[i]
return dp

• func productExceptSelf(nums []int) []int {
n := len(nums)
ans := make([]int, n)
left, right := 1, 1
for i, x := range nums {
ans[i] = left
left *= x
}
for i := n - 1; i >= 0; i-- {
ans[i] *= right
right *= nums[i]
}
return ans
}

• function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const ans: number[] = new Array(n);
for (let i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (let i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}


• /**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function (nums) {
const n = nums.length;
const ans = new Array(n);
for (let i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (let i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
};


• class Solution {
/**
* @param Integer[] $nums * @return Integer[] */ function productExceptSelf($nums) {
$n = count($nums);
$ans = []; for ($i = 0, $left = 1;$i < $n; ++$i) {
$ans[$i] = $left;$left *= $nums[$i];
}
for ($i =$n - 1, $right = 1;$i >= 0; --$i) {$ans[$i] *=$right;
$right *=$nums[$i]; } return$ans;
}
}

• public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] ans = new int[n];
for (int i = 0, left = 1; i < n; ++i) {
ans[i] = left;
left *= nums[i];
}
for (int i = n - 1, right = 1; i >= 0; --i) {
ans[i] *= right;
right *= nums[i];
}
return ans;
}
}

• impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![1; n];
for i in 1..n {
ans[i] = ans[i - 1] * nums[i - 1];
}
let mut r = 1;
for i in (0..n).rev() {
ans[i] *= r;
r *= nums[i];
}
ans
}
}