Product of Array Except Self (LeetCode
Learn how to solve Product of Array Except Self using brute force, division, prefix and suffix arrays, and the optimal O(1) extra-space approach. Includes intuition, dry runs, Java code, complexity analysis, zero handling, interview tips, and production applications.
Introduction
Product of Array Except Self is one of the most frequently asked array interview problems.
It is commonly associated with companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
This problem tests your understanding of:
- Prefix and suffix computation
- Array preprocessing
- Space optimization
- Zero handling
- Avoiding division
- Multi-pass algorithms
- Time and space complexity
The most important insight is:
The product for each index can be calculated by multiplying the product of all values to its left with the product of all values to its right.
Problem Statement
Given an integer array nums, return an array answer where:
answer[i]
is equal to the product of all elements in nums except nums[i].
Requirements:
- Do not use division.
- Solve the problem in
O(n)time. - The output array does not count as extra space for the space-complexity analysis.
Example 1
Input
nums = [1,2,3,4]
Output
[24,12,8,6]
Explanation:
answer[0] = 2 × 3 × 4 = 24
answer[1] = 1 × 3 × 4 = 12
answer[2] = 1 × 2 × 4 = 8
answer[3] = 1 × 2 × 3 = 6
Example 2
Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]
Only the position containing zero receives the product of all non-zero values.
Core Observation
For every index i:
answer[i]
=
Product of elements before i
×
Product of elements after i
For:
nums = [1,2,3,4]
At index 2:
Left Product
1 × 2 = 2
Right Product
4
Therefore:
answer[2] = 2 × 4 = 8
Approach 1 — Brute Force
Idea
For every index:
- Traverse the complete array.
- Multiply all values except the value at the current index.
- Store the result.
Brute Force Flow
graph TD
Current_Index["Current Index"] --> Scan_Entire_Array["Scan Entire Array"]
Scan_Entire_Array["Scan Entire Array"] --> Skip_Current_Index["Skip Current Index"]
Skip_Current_Index["Skip Current Index"] --> Multiply_Remaining_Values["Multiply Remaining Values"]
Multiply_Remaining_Values["Multiply Remaining Values"] --> Store_Result["Store Result"]
Java Code — Brute Force
public class ProductExceptSelfBruteForce {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int product = 1;
for (int j = 0; j < nums.length; j++) {
if (i != j) {
product *= nums[j];
}
}
answer[i] = product;
}
return answer;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1), excluding output |
This approach becomes inefficient for large arrays.
Approach 2 — Using Division
Idea
Calculate the product of all elements.
Then divide the total product by each element.
Example:
nums = [1,2,3,4]
Total Product = 24
Results:
graph TD
N_24_0_0["24"] --> N_24_1_1["24"]
N_24_0_0["24"] --> N_2_1_2["2"]
N_1_0_1["1"] --> N_12_1_3["12"]
N_24_1_1["24"] --> N_24_2_1["24"]
N_24_1_1["24"] --> N_3_2_2["3"]
N_2_1_2["2"] --> N_8_2_3["8"]
N_24_2_1["24"] --> N_24_3_1["24"]
N_24_2_1["24"] --> N_4_3_2["4"]
N_3_2_2["3"] --> N_6_3_3["6"]
Java Code — Division Approach
public class ProductExceptSelfUsingDivision {
public int[] productExceptSelf(int[] nums) {
int product = 1;
for (int number : nums) {
product *= number;
}
int[] answer = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
answer[i] = product / nums[i];
}
return answer;
}
}
Why the Division Approach Is Not Accepted
The problem explicitly states:
Do not use division.
It also fails when zero is present.
Example:
nums = [1,2,0,4]
The total product becomes:
0
Then:
0 / 0
is invalid.
Even with special zero handling, the solution violates the problem constraint.
Approach 3 — Prefix and Suffix Arrays
Core Idea
Create two arrays:
prefix[i]stores the product of all elements before indexi.suffix[i]stores the product of all elements after indexi.
Then:
answer[i] = prefix[i] × suffix[i]
Prefix Product Definition
For:
nums = [1,2,3,4]
Prefix products:
prefix[0] = 1
prefix[1] = 1
prefix[2] = 1 × 2 = 2
prefix[3] = 1 × 2 × 3 = 6
Result:
prefix = [1,1,2,6]
The first prefix value is 1 because there are no values before index 0.
Suffix Product Definition
For:
nums = [1,2,3,4]
Suffix products:
suffix[3] = 1
suffix[2] = 4
suffix[1] = 3 × 4 = 12
suffix[0] = 2 × 3 × 4 = 24
Result:
suffix = [24,12,4,1]
The last suffix value is 1 because there are no values after the last index.
Combine Prefix and Suffix
answer[i] = prefix[i] × suffix[i]
| Index | Prefix | Suffix | Answer |
|---|---|---|---|
| 0 | 1 | 24 | 24 |
| 1 | 1 | 12 | 12 |
| 2 | 2 | 4 | 8 |
| 3 | 6 | 1 | 6 |
Final result:
[24,12,8,6]
Java Code — Prefix and Suffix Arrays
public class ProductExceptSelfUsingArrays {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] prefix = new int[length];
int[] suffix = new int[length];
int[] answer = new int[length];
prefix[0] = 1;
for (int i = 1; i < length; i++) {
prefix[i] =
prefix[i - 1] * nums[i - 1];
}
suffix[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
suffix[i] =
suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < length; i++) {
answer[i] =
prefix[i] * suffix[i];
}
return answer;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(n), excluding output |
This solution is efficient but uses two additional arrays.
Approach 4 — Optimal Prefix and Suffix Product
Core Idea
We can avoid separate prefix and suffix arrays.
Use the output array to store prefix products first.
Then traverse from right to left while maintaining a running suffix product.
Step 1 — Store Prefix Products in Answer
For:
nums = [1,2,3,4]
Build:
answer = [1,1,2,6]
Each position contains the product of all values to its left.
Step 2 — Multiply by Running Suffix Product
Start with:
suffix = 1
Traverse from right to left.
At each index:
answer[i] = answer[i] × suffix
Then update:
suffix = suffix × nums[i]
Dry Run
Input
nums = [1,2,3,4]
Prefix Pass
Initialize:
answer[0] = 1
Index 1
answer[1]
=
answer[0] × nums[0]
=
1 × 1
=
1
Index 2
answer[2]
=
answer[1] × nums[1]
=
1 × 2
=
2
Index 3
answer[3]
=
answer[2] × nums[2]
=
2 × 3
=
6
After the prefix pass:
answer = [1,1,2,6]
Suffix Pass
Initialize:
suffix = 1
Index 3
answer[3] = 6 × 1 = 6
suffix = 1 × 4 = 4
Array:
[1,1,2,6]
Index 2
answer[2] = 2 × 4 = 8
suffix = 4 × 3 = 12
Array:
[1,1,8,6]
Index 1
answer[1] = 1 × 12 = 12
suffix = 12 × 2 = 24
Array:
[1,12,8,6]
Index 0
answer[0] = 1 × 24 = 24
suffix = 24 × 1 = 24
Final result:
[24,12,8,6]
Dry Run Table
| Index | Prefix Stored | Suffix Before | Final Value | Suffix After |
|---|---|---|---|---|
| 3 | 6 | 1 | 6 | 4 |
| 2 | 2 | 4 | 8 | 12 |
| 1 | 1 | 12 | 12 | 24 |
| 0 | 1 | 24 | 24 | 24 |
Java Code — Optimal Solution
public class ProductOfArrayExceptSelf {
public int[] productExceptSelf(int[] nums) {
int length = nums.length;
int[] answer = new int[length];
answer[0] = 1;
for (int i = 1; i < length; i++) {
answer[i] =
answer[i - 1] * nums[i - 1];
}
int suffixProduct = 1;
for (int i = length - 1; i >= 0; i--) {
answer[i] *= suffixProduct;
suffixProduct *= nums[i];
}
return answer;
}
}
Cleaner Java Implementation
public class Solution {
public int[] productExceptSelf(int[] nums) {
int[] result = new int[nums.length];
int prefix = 1;
for (int i = 0; i < nums.length; i++) {
result[i] = prefix;
prefix *= nums[i];
}
int suffix = 1;
for (int i = nums.length - 1;
i >= 0;
i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}
}
This version maintains both prefix and suffix values as running variables.
Complexity Analysis
| Complexity | Value |
|---|---|
| Time | O(n) |
| Extra Space | O(1), excluding output |
The array is traversed twice.
No additional prefix or suffix arrays are required.
Why Does the Optimal Algorithm Work?
During the first traversal:
result[i]
stores the product of all elements to the left of i.
During the second traversal:
suffix
stores the product of all elements to the right of i.
Multiplying them gives:
Left Product × Right Product
which excludes the current value automatically.
Visual Explanation
nums
[1,2,3,4]
Prefix products
[1,1,2,6]
Suffix running products
Index 3 → 1
Index 2 → 4
Index 1 → 12
Index 0 → 24
Final
[24,12,8,6]
Handling Zeroes
The prefix and suffix approach naturally handles zeroes without special logic.
Case 1 — One Zero
Input:
[1,2,0,4]
Expected output:
[0,0,8,0]
Explanation:
- Every position except the zero position includes zero in its product.
- At the zero position, multiply all non-zero values.
1 × 2 × 4 = 8
Dry Run with One Zero
Prefix products:
[1,1,2,0]
Suffix processing produces:
[0,0,8,0]
No separate zero check is needed.
Case 2 — Two Zeroes
Input:
[1,0,3,0]
Output:
[0,0,0,0]
Every result includes at least one zero.
Case 3 — No Zeroes
Input:
[2,3,4]
Output:
[12,8,6]
Edge Cases
Two Elements
Input
[5,10]
Output
[10,5]
Negative Values
Input
[-1,2,-3,4]
Output
[-24,12,-8,6]
All Ones
Input
[1,1,1,1]
Output
[1,1,1,1]
One Zero
Input
[2,0,4]
Output
[0,8,0]
Multiple Zeroes
Input
[0,2,0,4]
Output
[0,0,0,0]
Integer Overflow Consideration
The product may exceed the range of int in general applications.
The LeetCode problem guarantees that prefix and suffix products fit within a 32-bit integer.
In production systems, consider using:
long
Example:
public long[] productExceptSelf(long[] nums) {
long[] result = new long[nums.length];
long prefix = 1L;
for (int i = 0; i < nums.length; i++) {
result[i] = prefix;
prefix *= nums[i];
}
long suffix = 1L;
for (int i = nums.length - 1;
i >= 0;
i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}
For financial applications, also verify whether multiplication or decimal precision is appropriate.
Comparison of Approaches
| Approach | Time | Extra Space | Handles Zeroes | Uses Division |
|---|---|---|---|---|
| Brute Force | O(n²) | O(1) | Yes | No |
| Total Product | O(n) | O(1) | Requires special handling | Yes |
| Prefix + Suffix Arrays | O(n) | O(n) | Yes | No |
| Optimized Prefix + Suffix | O(n) | O(1) excluding output | Yes | No |
The optimized prefix and suffix approach is the best solution.
Common Interview Mistakes
Mistake 1 — Using Division
The problem explicitly prohibits division.
It also creates complications when zeroes are present.
Mistake 2 — Multiplying the Current Element
The output for index i must exclude:
nums[i]
The prefix and suffix definitions should not include the current position.
Mistake 3 — Incorrect Prefix Initialization
The first prefix product must be:
1
because there are no elements to the left of index 0.
Mistake 4 — Incorrect Suffix Initialization
The running suffix product must begin with:
1
because there are no elements to the right of the final index.
Mistake 5 — Updating Suffix Too Early
Correct order:
result[i] *= suffix;
suffix *= nums[i];
Incorrect order:
suffix *= nums[i];
result[i] *= suffix;
The incorrect version includes the current element.
Mistake 6 — Claiming O(1) Total Space
The result array requires O(n) memory.
The accepted statement is:
O(1) extra space, excluding the output array
Mistake 7 — Ignoring Integer Overflow
For production systems, consider long or arbitrary-precision types when input ranges are not constrained.
Production Applications
The prefix and suffix technique is useful in:
- Financial risk calculations
- Portfolio contribution analysis
- Product-weight aggregation
- Sensor impact calculations
- Statistical processing
- Data normalization pipelines
- Recommendation scoring
- Probability calculations
- Distributed analytics
- Batch-processing systems
Real-World Example — Portfolio Contribution
Suppose a system stores multiplicative risk factors:
[2,3,5,7]
To determine the combined factor excluding each individual source:
Exclude 2 → 3 × 5 × 7 = 105
Exclude 3 → 2 × 5 × 7 = 70
Exclude 5 → 2 × 3 × 7 = 42
Exclude 7 → 2 × 3 × 5 = 30
Result:
[105,70,42,30]
The same prefix and suffix strategy computes all results in linear time.
Real-World Example — Service Reliability
Suppose several independent reliability ratios are represented as scaled integer values.
A system may need to calculate the combined reliability contribution of all services except one.
Prefix and suffix products avoid recalculating the complete product for every service.
For real probability calculations, use appropriate decimal or floating-point types and consider numerical precision.
Follow-Up Question 1 — What If Division Is Allowed?
If no zero exists:
- Calculate total product.
- Divide by each element.
However, zero handling becomes more complicated.
Cases:
- No zero: divide normally.
- One zero: only the zero position receives the product of non-zero elements.
- More than one zero: all results are zero.
The prefix and suffix approach remains cleaner.
Follow-Up Question 2 — What If the Input Cannot Be Modified?
The optimal solution does not modify the input.
It creates only the required output array.
Follow-Up Question 3 — Can This Be Solved in One Pass?
In a conventional array implementation, the clean solution uses two passes:
- Left-to-right for prefix values
- Right-to-left for suffix values
Both passes together still require:
O(n)
time.
Trying to force the solution into one pass usually makes it less readable without improving asymptotic complexity.
Follow-Up Question 4 — What If the Input Is Very Large?
Consider:
- Streaming chunks
- Parallel prefix algorithms
- Distributed prefix scans
- Overflow handling
- Memory-mapped storage
However, computing each output requires information from both sides, so simple one-direction streaming is insufficient without storing intermediate state.
Follow-Up Question 5 — Can Parallel Processing Help?
Yes, prefix products can be generalized using parallel scan algorithms.
However:
- Parallel coordination adds overhead.
- Integer overflow remains a concern.
- For normal interview-sized arrays, the sequential
O(n)solution is preferred.
Follow-Up Question 6 — What If Products Are Extremely Large?
Possible solutions include:
longBigInteger- Logarithmic transformation for approximate comparisons
- Modular arithmetic when the problem defines a modulus
Example using BigInteger:
import java.math.BigInteger;
public class ProductExceptSelfBigInteger {
public BigInteger[] productExceptSelf(
int[] nums) {
BigInteger[] result =
new BigInteger[nums.length];
BigInteger prefix =
BigInteger.ONE;
for (int i = 0; i < nums.length; i++) {
result[i] = prefix;
prefix = prefix.multiply(
BigInteger.valueOf(nums[i]));
}
BigInteger suffix =
BigInteger.ONE;
for (int i = nums.length - 1;
i >= 0;
i--) {
result[i] =
result[i].multiply(suffix);
suffix = suffix.multiply(
BigInteger.valueOf(nums[i]));
}
return result;
}
}
Interview Explanation
A strong interview explanation could be:
For each index, the required result is the product of all values to its left multiplied by the product of all values to its right. I first store prefix products directly in the output array. Then I traverse from right to left using a running suffix product and multiply it into each output position. This avoids division, handles zeroes naturally, and achieves O(n) time with O(1) extra space excluding the output array.
Interview Tips
Interviewers commonly ask:
- Why can division not be used?
- How do prefix and suffix products work?
- Why initialize prefix and suffix with
1? - How does the solution handle one zero?
- What happens with two zeroes?
- Why is the solution O(n)?
- Why is the extra space O(1)?
- Can integer overflow occur?
- Can it be solved in one pass?
- How would you handle very large products?
Explain the left-product and right-product idea before writing code.
Unit Tests
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.Test;
class ProductOfArrayExceptSelfTest {
private final ProductOfArrayExceptSelf solution =
new ProductOfArrayExceptSelf();
@Test
void shouldCalculateProductsForPositiveNumbers() {
int[] nums = {1, 2, 3, 4};
assertArrayEquals(
new int[]{24, 12, 8, 6},
solution.productExceptSelf(nums));
}
@Test
void shouldHandleSingleZero() {
int[] nums = {1, 2, 0, 4};
assertArrayEquals(
new int[]{0, 0, 8, 0},
solution.productExceptSelf(nums));
}
@Test
void shouldHandleMultipleZeroes() {
int[] nums = {1, 0, 3, 0};
assertArrayEquals(
new int[]{0, 0, 0, 0},
solution.productExceptSelf(nums));
}
@Test
void shouldHandleNegativeNumbers() {
int[] nums = {-1, 2, -3, 4};
assertArrayEquals(
new int[]{-24, 12, -8, 6},
solution.productExceptSelf(nums));
}
@Test
void shouldHandleTwoElements() {
int[] nums = {5, 10};
assertArrayEquals(
new int[]{10, 5},
solution.productExceptSelf(nums));
}
}
Summary
The Product of Array Except Self problem demonstrates how preprocessing can eliminate repeated calculations.
The brute-force approach recalculates the product for every index and requires O(n²) time.
The prefix and suffix strategy computes all results in linear time.
The optimal version stores prefix products in the output array and uses a running suffix value during the reverse traversal.
Optimal complexity:
Time: O(n)
Extra Space: O(1), excluding output
It also handles zeroes naturally without division or special-case logic.
Key Takeaways
- Each result equals the left product multiplied by the right product.
- Avoid recalculating the product for every index.
- Do not use division.
- Store prefix products in the output array.
- Use a running suffix product from right to left.
- Initialize prefix and suffix values with
1. - Update the result before multiplying the current value into the suffix.
- Handle one or multiple zeroes naturally.
- Achieve O(n) time complexity.
- Use O(1) extra space excluding the output array.
- Consider overflow in production systems.
- Explain the two-pass logic clearly during interviews.