Product of Array Except Self
Product of Array except Self Problem – Medium Level
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
Each product is guaranteed to fit in a 32-bit integer.
Follow-up: Could you solve it in O(n) time without using the division operation?
Output: [48,24,12,8]
Output: [0,-6,0,0,0]
Constraints:
- 2 <= nums.length <= 1000
- -20 <= nums[i] <= 20
Product of Array Except Self Solution
Recommendation for Time and Space Complexity – You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute-force solution would be to iterate through the array with index i and compute the product of the array except for that index element. This would be an O(n^2) solution. Can you think of a better way?
Hint 2 :
Is there a way to avoid the repeated work? Maybe we can store the results of the repeated work in an array.
Hint 3 :
We can use the prefix and suffix technique. First, we iterate from left to right and store the prefix products for each index in a prefix array, excluding the current index’s number. Then, we iterate from right to left and store the suffix products for each index in a suffix array, also excluding the current index’s number. Can you figure out the solution from here?
Hint 4 :
We can use the stored prefix and suffix products to compute the result array by iterating through the array and simply multiplying the prefix and suffix products at each index.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Division Method
- Prefix and Suffix Method
- Prefix and Suffix Method(Optimal)
1. Brute Force Method
This method helps like for each element, calculate the product of all other elements by iterating through the array.
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
class Solution {
public:
vector productExceptSelf(vector& nums) {
int n = nums.size();
vector res(n);
for (int i = 0; i < n; i++) {
int prod = 1;
for (int j = 0; j < n; j++) {
if (i != j) {
prod *= nums[j];
}
}
res[i] = prod;
}
return res;
}
};
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
for (int i = 0; i < n; i++) {
int prod = 1;
for (int j = 0; j < n; j++) {
if (i != j) {
prod *= nums[j];
}
}
res[i] = prod;
}
return res;
}
}
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
for i in range(n):
prod = 1
for j in range(n):
if i == j:
continue
prod *= nums[j]
res[i] = prod
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[]}
*/
productExceptSelf(nums) {
const n = nums.length;
const res = new Array(n);
for (let i = 0; i < n; i++) {
let prod = 1;
for (let j = 0; j < n; j++) {
if (i !== j) {
prod *= nums[j];
}
}
res[i] = prod;
}
return res;
}
}
2. Division Method
This method calculate the total product of the array, then divide it by each element to get the result. Not applicable if the array contains zeros.
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
vector productExceptSelf(vector& nums) {
int prod = 1, zeroCount = 0;
for (int num : nums) {
if (num != 0) {
prod *= num;
} else {
zeroCount++;
}
}
if (zeroCount > 1) {
return vector(nums.size(), 0);
}
vector res(nums.size());
for (size_t i = 0; i < nums.size(); i++) {
if (zeroCount > 0) {
res[i] = (nums[i] == 0) ? prod : 0;
} else {
res[i] = prod / nums[i];
}
}
return res;
}
};
public class Solution {
public int[] productExceptSelf(int[] nums) {
int prod = 1, zeroCount = 0;
for (int num : nums) {
if (num != 0) {
prod *= num;
} else {
zeroCount++;
}
}
if (zeroCount > 1) {
return new int[nums.length];
}
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (zeroCount > 0) {
res[i] = (nums[i] == 0) ? prod : 0;
} else {
res[i] = prod / nums[i];
}
}
return res;
}
}
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
prod, zero_cnt = 1, 0
for num in nums:
if num:
prod *= num
else:
zero_cnt += 1
if zero_cnt > 1: return [0] * len(nums)
res = [0] * len(nums)
for i, c in enumerate(nums):
if zero_cnt: res[i] = 0 if c else prod
else: res[i] = prod // c
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[]}
*/
productExceptSelf(nums) {
let prod = 1;
let zeroCount = 0;
for (let num of nums) {
if (num !== 0) {
prod *= num;
} else {
zeroCount++;
}
}
if (zeroCount > 1) {
return Array(nums.length).fill(0);
}
const res = new Array(nums.length);
for (let i = 0; i < nums.length; i++) {
if (zeroCount > 0) {
res[i] = (nums[i] === 0) ? prod : 0;
} else {
res[i] = prod / nums[i];
}
}
return res;
}
}
3. Prefix and Suffix Method
This method precompute prefix and suffix products for each element and multiply them to get the result for every index.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector productExceptSelf(vector& nums) {
int n = nums.size();
vector res(n);
vector pref(n);
vector suff(n);
pref[0] = 1;
suff[n - 1] = 1;
for (int i = 1; i < n; i++) {
pref[i] = nums[i - 1] * pref[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
suff[i] = nums[i + 1] * suff[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = pref[i] * suff[i];
}
return res;
}
};
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int[] pref = new int[n];
int[] suff = new int[n];
pref[0] = 1;
suff[n - 1] = 1;
for (int i = 1; i < n; i++) {
pref[i] = nums[i - 1] * pref[i - 1];
}
for (int i = n - 2; i >= 0; i--) {
suff[i] = nums[i + 1] * suff[i + 1];
}
for (int i = 0; i < n; i++) {
res[i] = pref[i] * suff[i];
}
return res;
}
}
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
pref = [0] * n
suff = [0] * n
pref[0] = suff[n - 1] = 1
for i in range(1, n):
pref[i] = nums[i - 1] * pref[i - 1]
for i in range(n - 2, -1, -1):
suff[i] = nums[i + 1] * suff[i + 1]
for i in range(n):
res[i] = pref[i] * suff[i]
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[]}
*/
productExceptSelf(nums) {
const n = nums.length;
const res = new Array(n);
const pref = new Array(n);
const suff = new Array(n);
pref[0] = 1;
suff[n - 1] = 1;
for (let i = 1; i < n; i++) {
pref[i] = nums[i - 1] * pref[i - 1];
}
for (let i = n - 2; i >= 0; i--) {
suff[i] = nums[i + 1] * suff[i + 1];
}
for (let i = 0; i < n; i++) {
res[i] = pref[i] * suff[i];
}
return res;
}
}
4. Prefix and Suffix Method(Optimal)
This method compute the prefix product in one pass and use it to calculate the suffix product directly during a second pass, achieving O(n) time with O(1) space (excluding the result array).
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
vector productExceptSelf(vector& nums) {
int n = nums.size();
vector res(n, 1);
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int postfix = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= postfix;
postfix *= nums[i];
}
return res;
}
};
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int postfix = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= postfix;
postfix *= nums[i];
}
return res;
}
}
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * (len(nums))
prefix = 1
for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[]}
*/
productExceptSelf(nums) {
const n = nums.length;
const res = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
let postfix = 1;
for (let i = n - 1; i >= 0; i--) {
res[i] *= postfix;
postfix *= nums[i];
}
return res;
}
}
