Product of Array Except Self — Prefix and Suffix Multiplication
Compute prefix products and suffix products to fill the output without division.
Problem Statement
Given an integer array nums, return an array output such that output[i] equals the product of all elements except nums[i] without using division.
Why This Problem Matters
- Practices prefix/suffix accumulation strategies.
- Avoids division pitfalls when zeros are present.
- Common interview question assessing space-time trade-offs.
Thought Process
Compute prefix products
Store product of numbers to the left of each index.
Multiply by suffix products
Traverse from the right accumulating suffix product and multiply into result.
Handle zeros implicitly
Prefix/suffix approach naturally accounts for zero counts without division.
Step-by-Step Reasoning
- Initialise output array with prefix products: output[i] = output[i-1] * nums[i-1].
- Set suffix = 1 and traverse from end to start, multiplying output[i] *= suffix then suffix *= nums[i].
- Return output.
Dry Run
nums = [1,2,3,4]
Output becomes [24,12,8,6].
nums = [-1,1,0,-3,3]
Output becomes [0,0,9,0,0] handling zeros gracefully.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Two passes with constant extra variables aside from output array.
Annotated Solution
public class ProductOfArrayExceptSelf {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] output = new int[n];
output[0] = 1;
for (int i = 1; i < n; i += 1) {
output[i] = output[i - 1] * nums[i - 1];
}
int suffix = 1;
for (int i = n - 1; i >= 0; i -= 1) {
output[i] *= suffix;
suffix *= nums[i];
}
return output;
}
}Prefix array stores product to the left; suffix variable accumulates product to the right and multiplies into output in reverse pass.
Common Pitfalls
- Multiplying into result before storing prefix leads to using current element incorrectly.
- Using int may overflow; mention using long if constraints require.
- Attempting to divide by product fails with zeros; emphasise prefix approach instead.
Follow-Up Questions
- Can you solve it in-place for languages allowing modification of input?
- How would you adapt it for modulo arithmetic?