Array Product Exclusions — Problem Statement & Solution Guide
Problem Description
Given an array of integers, compute an array where each element at index i is the product of all numbers in the array except for the one at index i. If the input array contains more than one zero, return an array of zeros. If the input array contains exactly one zero, return an array where the zero is replaced with the product of all non-zero numbers, and all other elements are zero.
Examples
Input
[1, 2, 3, 4]
Output
[24, 12, 8, 6]
Explanation: Step-by-step: with input [1, 2, 3, 4], we calculate the product of all numbers except for the one at each index. For index 0, the product is 2*3*4 = 24. For index 1, the product is 1*3*4 = 12. For index 2, the product is 1*2*4 = 8. For index 3, the product is 1*2*3 = 6. So the output is [24, 12, 8, 6].
Input
[0, 1, 2, 3]
Output
[6, 0, 0, 0]
Explanation: Step-by-step: with input [0, 1, 2, 3], we calculate the product of all non-zero numbers, which is 1*2*3 = 6. We replace the zero at index 0 with this product, and all other elements are zero. So the output is [6, 0, 0, 0].
Constraints
- 2 <= n <= 10^5
- -30 <= arr[i] <= 30
Optimal Approach & Strategy
Create answer array. First pass: store running prefix product into answer. Second pass: iterate backwards keeping a running suffix product, multiplying it into answer array. Time O(N), Space O(1) (excluding output array).
Brute Force Approach
Multiply all elements except the current one for each index. Time O(N^2).
Verified Code Solutions
function solution(nums) {
let zeroCount = 0;
let product = 1;
for (let num of nums) {
if (num === 0) {
zeroCount++;
} else {
product *= num;
}
}
if (zeroCount > 1) {
return new Array(nums.length).fill(0);
} else if (zeroCount === 1) {
return nums.map(num => num === 0 ? product : 0);
} else {
let result = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i !== j) {
result[i] *= nums[j];
}
}
}
return result;
}
}class Solution {
public:
vector<int> solution(vector<int>& nums) {
int zeroCount = 0;
int product = 1;
for (int num : nums) {
if (num == 0) {
zeroCount++;
} else {
product *= num;
}
}
if (zeroCount > 1) {
vector<int> result(nums.size(), 0);
return result;
} else if (zeroCount == 1) {
vector<int> result(nums.size());
for (int i = 0; i < nums.size(); i++) {
result[i] = nums[i] == 0 ? product : 0;
}
return result;
} else {
vector<int> result(nums.size(), 1);
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
if (i != j) {
result[i] *= nums[j];
}
}
}
return result;
}
}
};class Solution {
public int[] solution(int[] nums) {
int zeroCount = 0;
int product = 1;
for (int num : nums) {
if (num == 0) {
zeroCount++;
} else {
product *= num;
}
}
if (zeroCount > 1) {
int[] result = new int[nums.length];
return result;
} else if (zeroCount == 1) {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = nums[i] == 0 ? product : 0;
}
return result;
} else {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = 1;
for (int j = 0; j < nums.length; j++) {
if (i != j) {
result[i] *= nums[j];
}
}
}
return result;
}
}
}def solution(nums):
zero_count = 0
product = 1
for num in nums:
if num == 0:
zero_count += 1
else:
product *= num
if zero_count > 1:
return [0] * len(nums)
elif zero_count == 1:
return [product if num == 0 else 0 for num in nums]
else:
result = [1] * len(nums)
for i in range(len(nums)):
for j in range(len(nums)):
if i != j:
result[i] *= nums[j]
return resultfunction solution(nums) {
let zeroCount = 0;
let product = 1;
for (let num of nums) {
if (num === 0) {
zeroCount++;
} else {
product *= num;
}
}
if (zeroCount > 1) {
return new Array(nums.length).fill(0);
} else if (zeroCount === 1) {
return nums.map(num => num === 0 ? product : 0);
} else {
let result = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
if (i !== j) {
result[i] *= nums[j];
}
}
}
return result;
}
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.