• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n);        // can also use nums as the ans array
vector<int> prefix(n, 1);  // prefix product
vector<int> suffix(n, 1);  // suffix product

for (int i = 1; i < n; ++i)
prefix[i] = prefix[i - 1] * nums[i - 1];

for (int i = n - 2; i >= 0; --i)
suffix[i] = suffix[i + 1] * nums[i + 1];

for (int i = 0; i < n; ++i)
ans[i] = prefix[i] * suffix[i];

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] productExceptSelf(int[] nums) {
final int n = nums.length;
int[] ans = new int[n];    // can also use nums as the ans array
int[] prefix = new int[n]; // prefix product
int[] suffix = new int[n]; // suffix product

prefix[0] = 1;
for (int i = 1; i < n; ++i)
prefix[i] = prefix[i - 1] * nums[i - 1];

suffix[n - 1] = 1;
for (int i = n - 2; i >= 0; --i)
suffix[i] = suffix[i + 1] * nums[i + 1];

for (int i = 0; i < n; ++i)
ans[i] = prefix[i] * suffix[i];

return ans;
}
}
``````

## Python

``````class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
prefix = [1] * n  # prefix product
suffix = [1] * n  # suffix product

for i in range(1, n):
prefix[i] = prefix[i - 1] * nums[i - 1]

for i in reversed(range(n - 1)):
suffix[i] = suffix[i + 1] * nums[i + 1]

return [prefix[i] * suffix[i] for i in range(n)]
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
const int n = nums.size();
vector<int> ans(n, 1);

// use ans as the prefix product array
for (int i = 1; i < n; ++i)
ans[i] = ans[i - 1] * nums[i - 1];

int suffix = 1;  // suffix product
for (int i = n - 1; i >= 0; --i) {
ans[i] *= suffix;
suffix *= nums[i];
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] productExceptSelf(int[] nums) {
final int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;

// use ans as the prefix product array
for (int i = 1; i < n; ++i)
ans[i] = ans[i - 1] * nums[i - 1];

int suffix = 1; // suffix product
for (int i = n - 1; i >= 0; --i) {
ans[i] *= suffix;
suffix *= nums[i];
}

return ans;
}
}
``````

## Python

``````class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n

# use ans as the prefix product array
for i in range(1, n):
ans[i] = ans[i - 1] * nums[i - 1]

suffix = 1  # suffix product
for i, num in reversed(list(enumerate(nums))):
ans[i] *= suffix
suffix *= num

return ans
``````