Product of Array Except Self: Without Division
The Prompt
Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. You must write an algorithm that runs in O(n) time and without using the division operation.
Understanding the Problem
For each index you want the product of everything else. The naive version multiplies n ā 1 numbers for each of n positions ā O(nĀ²). The "obvious" fix, dividing the total product by nums[i], is banned by the problem (and would break on zeros anyway), so the challenge is genuinely structural.
The structural insight: the product of everything except nums[i] splits cleanly into (product of everything left of i) Ć (product of everything right of i). Prefix products are computable in one left-to-right pass, suffix products in one right-to-left pass ā so two passes cover every index.
The Interview Flow
Interviewer
Let's discuss this problem: for an array, compute a new array where each element is the product of all other elements. The catch is, you can't use division and it must be O(n).
Candidate
Without division is the key constraint. If I could use it, I would just find the total product of the array and then for each element, divide the total product by that element.
Interviewer
Correct. So how can we do it without division?
Candidate
The product at index `i` is essentially (product of all elements to the left of `i`) * (product of all elements to the right of `i`). I can compute these prefix and postfix products.
Interviewer
How would you do that efficiently?
Candidate
I can create two arrays: one for prefix products and one for postfix products. I'd iterate from left to right to fill the prefix array, and from right to left for the postfix array. Then, I can iterate a third time and for each index `i`, the result would be `prefix[i-1] * postfix[i+1]`. This would use O(n) space for the extra arrays.
Interviewer
That's a solid O(n) time and O(n) space solution. Can you optimize the space complexity to O(1) (excluding the output array)?
Candidate
Yes. I can use the result array itself to store the products. First, I can iterate from left to right, filling the result array with the prefix products. Then, I can iterate from right to left. In this second pass, I'll maintain a variable for the postfix product, multiply it with the existing value in the result array, and then update the postfix product variable. This way, I only need one extra variable, achieving O(1) space.
Interviewer
Perfect. That's the optimal solution. Please code it.
Why do two passes give O(1) extra space?
Pass one walks left to right carrying a running prefix: at each i it writes the product of nums[0..iā1] into result[i] before folding nums[i] into the prefix. Pass two walks right to left carrying a running postfix and multiplies it into result[i] before folding nums[i] in. After both passes, result[i] = (left product) Ć (right product) ā exactly the answer, and no element ever multiplied itself.
Time is O(n) ā two linear passes. Space is O(1) beyond the output because both running products live in single variables and the answer array doubles as scratch space for the prefix pass. That reuse of the output buffer is the detail interviewers listen for.
O(1) Space Solution using Prefix and Postfix Products
- Initialize a result array of the same size as `nums`, with all values set to 1.
- Initialize a prefix product variable to 1.
- Iterate through `nums` from left to right (from index 0 to n-1). For each index `i`, set `result[i] = prefix`. Then, update the prefix product by multiplying it with `nums[i]`. After this loop, `result[i]` will contain the product of all elements to its left.
- Initialize a postfix product variable to 1.
- Iterate through `nums` from right to left (from index n-1 to 0). For each index `i`, multiply the current `result[i]` by the postfix product. Then, update the postfix product by multiplying it with `nums[i]`.
- After both passes, the `result` array will contain the final desired products. Return it.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function productExceptSelf(nums) {
const n = nums.length;
const answer = new Array(n).fill(1);
let prefix = 1;
for (let i = 0; i < n; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
let postfix = 1;
for (let i = n - 1; i >= 0; i--) {
answer[i] *= postfix;
postfix *= nums[i];
}
return answer;
}Explanation
Run nums = [1, 2, 3, 4], whose answer is [24, 12, 8, 6].
1Prefix pass (left ā right): result[i] gets the product of everything before i. result = [1, 1, 1Ć2 = 2, 1Ć2Ć3 = 6].
2Suffix pass (right ā left) with postfix = 1: i = 3 ā result[3] = 6 Ć 1 = 6, postfix becomes 4. i = 2 ā result[2] = 2 Ć 4 = 8, postfix becomes 3 Ć 4 = 12.
3i = 1 ā result[1] = 1 Ć 12 = 12, postfix becomes 2 Ć 12 = 24. i = 0 ā result[0] = 1 Ć 24 = 24. Final answer: [24, 12, 8, 6].
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.