.png)
Product of Array Except Self
Problem Statement
You are given an array of integers arr of size n.
Your task is to return an array output such that:
output[i] = product of all elements of arr except arr[i]
Constraints
- Do not use division (in the optimal approach)
- Solve in O(n) time
Example 1
Input
arr = [1, 2, 3, 4]
Output
[24, 12, 8, 6]
Example 2
Input
arr = [-1, 1, 0, -3, 3]
Output
[0, 0, 9, 0, 0]
Why This Problem Is Important
- Very frequently asked interview problem
- Tests array traversal and prefix logic
- Tests space optimization
- Appears in FAANG interviews
- Builds foundation for prefix & suffix techniques
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Using Division | O(n) | O(1) |
| Approach 3 | Prefix & Suffix Product (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
For each index, calculate the product of all elements except the current one using nested loops.
Algorithm
- Initialize an output array
- For each index i
- Set product = 1
- Loop through array
- Multiply all elements except i
- Store product in output array
Time & Space Complexity
- Time: O(n²)
- Space: O(1) (excluding output array)
Implementations
C
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int output[4];
for(int i = 0; i < n; i++) {
int prod = 1;
for(int j = 0; j < n; j++) {
if(i != j)
prod *= arr[j];
}
output[i] = prod;
}
for(int i = 0; i < n; i++)
printf("%d ", output[i]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int output[4];
for(int i = 0; i < n; i++) {
int prod = 1;
for(int j = 0; j < n; j++) {
if(i != j)
prod *= arr[j];
}
output[i] = prod;
}
for(int i = 0; i < n; i++)
cout << output[i] << " ";
return 0;
}
Java
public class ProductExceptSelf {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
int n = arr.length;
int[] output = new int[n];
for(int i = 0; i < n; i++) {
int prod = 1;
for(int j = 0; j < n; j++) {
if(i != j)
prod *= arr[j];
}
output[i] = prod;
}
for(int val : output)
System.out.print(val + " ");
}
}
Python
arr = [1,2,3,4]
n = len(arr)
output = []
for i in range(n):
prod = 1
for j in range(n):
if i != j:
prod *= arr[j]
output.append(prod)
print(output)
JavaScript
let arr = [1,2,3,4];
let output = [];
for (let i = 0; i < arr.length; i++) {
let prod = 1;
for (let j = 0; j < arr.length; j++) {
if (i !== j)
prod *= arr[j];
}
output.push(prod);
}
console.log(output);
Approach 2: Using Division
Idea
Compute total product of all elements.
For each index, divide total product by arr[i].
⚠️ Fails when array contains zero(s)
Algorithm
- Compute total product
- For each index i, output = totalProduct / arr[i]
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int product = 1;
for(int i = 0; i < n; i++)
product *= arr[i];
for(int i = 0; i < n; i++)
printf("%d ", product / arr[i]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int product = 1;
for(int i = 0; i < n; i++)
product *= arr[i];
for(int i = 0; i < n; i++)
cout << product / arr[i] << " ";
return 0;
}
Java
public class ProductExceptSelf {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
int product = 1;
for(int num : arr)
product *= num;
for(int num : arr)
System.out.print(product / num + " ");
}
}
Python
arr = [1,2,3,4]
product = 1
for num in arr:
product *= num
print([product // num for num in arr])
JavaScript
let arr = [1,2,3,4];
let product = 1;
for (let num of arr)
product *= num;
console.log(arr.map(num => product / num));
Approach 3: Prefix & Suffix Product (Optimal)
Idea
Instead of division, compute:
- Prefix product (left side)
- Suffix product (right side)
Multiply both for each index.
Algorithm
- Create output array initialized with 1
- Traverse left → right
- output[i] = product of elements before i
- Traverse right → left
- output[i] *= product of elements after i
Time & Space Complexity
- Time: O(n)
- Space: O(1) (excluding output array)
Implementations
C
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int output[4];
int prefix = 1;
for(int i = 0; i < n; i++) {
output[i] = prefix;
prefix *= arr[i];
}
int suffix = 1;
for(int i = n - 1; i >= 0; i--) {
output[i] *= suffix;
suffix *= arr[i];
}
for(int i = 0; i < n; i++)
printf("%d ", output[i]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int output[4];
int prefix = 1;
for(int i = 0; i < n; i++) {
output[i] = prefix;
prefix *= arr[i];
}
int suffix = 1;
for(int i = n - 1; i >= 0; i--) {
output[i] *= suffix;
suffix *= arr[i];
}
for(int i = 0; i < n; i++)
cout << output[i] << " ";
return 0;
}
Java
public class ProductExceptSelf {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
int n = arr.length;
int[] output = new int[n];
int prefix = 1;
for(int i = 0; i < n; i++) {
output[i] = prefix;
prefix *= arr[i];
}
int suffix = 1;
for(int i = n - 1; i >= 0; i--) {
output[i] *= suffix;
suffix *= arr[i];
}
for(int val : output)
System.out.print(val + " ");
}
}
Python
arr = [1,2,3,4]
n = len(arr)
output = [1] * n
prefix = 1
for i in range(n):
output[i] = prefix
prefix *= arr[i]
suffix = 1
for i in range(n-1, -1, -1):
output[i] *= suffix
suffix *= arr[i]
print(output)
JavaScript
let arr = [1,2,3,4];
let n = arr.length;
let output = Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) {
output[i] = prefix;
prefix *= arr[i];
}
let suffix = 1;
for (let i = n - 1; i >= 0; i--) {
output[i] *= suffix;
suffix *= arr[i];
}
console.log(output);
Dry Run (Prefix & Suffix)
Input
[1, 2, 3, 4]
- Prefix pass → [1, 1, 2, 6]
- Suffix pass → [24, 12, 8, 6]
Final Output
[24, 12, 8, 6]
Summary
- Brute force is inefficient
- Division method is simple but unsafe
- Prefix & Suffix approach is optimal and interview-preferred
- Solves in linear time without division
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
