Approach Summary
Two passes: left pass builds prefix products, right pass multiplies suffix products into the result array.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Prefix & Suffix Product Arrays | O(n) | O(n) | Allocate two helper arrays left[] and right[] to store prefix and suffix cumulative products. |
| 2 Approach 2: Running Suffix Accumulator (Optimal) | O(n) | O(1) auxiliary | Compute prefix products directly in output[], then accumulate suffix products backward in-place. |
Step 1: Baseline
Approach 1: Prefix & Suffix Product Arrays
Time: O(n)
Space: O(n)
Create `left[n]` where `left[i]` is the product of all elements to the left of index i, and `right[n]` where `right[i]` is the product of all elements to the right of index i. After precomputing both arrays in O(n), each `output[i] = left[i] * right[i]`. This requires 2 extra arrays of size n.
Approach 1: Prefix & Suffix Product Arrays Implementation
Approach 1: Prefix & Suffix Product Arrays
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int left[] = new int[n];
left[0] = 1;
for (int i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
int right[] = new int[n];
right[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
int output[] = new int[n];
for (int i = 0; i < n; i++) {
output[i] = left[i] * right[i];
}
return output;
}
}class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, 1);
for (int i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
vector<int> right(n, 1);
for (int i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
vector<int> output(n);
for (int i = 0; i < n; i++) {
output[i] = left[i] * right[i];
}
return output;
}
};def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
return [left[i] * right[i] for i in range(n)]function productExceptSelf(nums) {
const n = nums.length;
const left = new Array(n).fill(1);
const right = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
for (let i = n - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
const output = new Array(n);
for (let i = 0; i < n; i++) {
output[i] = left[i] * right[i];
}
return output;
} Step 2: Most Optimized
Approach 2: Running Suffix Accumulator (Optimal)
Time: O(n)
Space: O(1) auxiliary
Store the prefix products directly in `output`. In the first forward pass, `output[i] = output[i - 1] * nums[i - 1]`. Then maintain a running integer `rightProduct = 1` and iterate backward from n - 1 down to 0: multiply `output[i] *= rightProduct`, then update `rightProduct *= nums[i]`. This eliminates both extra arrays, matching the problem's follow-up constraint.
Approach 2: Running Suffix Accumulator (Optimal) Implementation
Approach 2: Running Suffix Accumulator (Optimal)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int output[] = new int[n];
output[0] = 1;
for (int i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
output[i] *= rightProduct;
rightProduct *= nums[i];
}
return output;
}
}class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> output(n, 1);
for (int i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}
int rightProduct = 1;
for (int i = n - 1; i >= 0; i--) {
output[i] *= rightProduct;
rightProduct *= nums[i];
}
return output;
}
};def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
output = [1] * n
for i in range(1, n):
output[i] = output[i - 1] * nums[i - 1]
right_product = 1
for i in range(n - 1, -1, -1):
output[i] *= right_product
right_product *= nums[i]
return outputfunction productExceptSelf(nums) {
const n = nums.length;
const output = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}
let rightProduct = 1;
for (let i = n - 1; i >= 0; i--) {
output[i] *= rightProduct;
rightProduct *= nums[i];
}
return output;
}Edge Cases to Watch
- Array containing a single 0 (that position gets the product of all other numbers, all other positions become 0)
- Array containing two or more 0s (every position evaluates to 0)
- Negative numbers flipping product signs
- Minimum length array (n = 2)
Algorithmic Pattern
View Pattern Guide →
Master the Prefix Sum Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Prefix Sum pattern.
Framework: Prefix Sum • Interview Prep: Tested at FAANG •
Explore all Prefix Sum problems & invariants →
How to Recognize This Pattern
- No division allowed
- Product of all except current
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Prefix Product
Frequently Asked Questions
What is the optimal time and space complexity for Product of Array Except Self?
The optimal solution for Product of Array Except Self achieves O(n) runtime complexity and requires O(1) auxiliary space. We iterate through the array twice (one forward pass and one backward pass), resulting in O(n) runtime. In Approach 2, the output array does not count toward auxiliary space complexity, so auxiliary space is strictly O(1).
How do I identify that Product of Array Except Self requires the Prefix Sum pattern?
In technical interviews, look for key problem signals: No division allowed; Product of all except current. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Prefix Sum strategy.
What critical edge cases must be handled in Product of Array Except Self?
Essential edge cases to verify include: Array containing a single 0 (that position gets the product of all other numbers, all other positions become 0); Array containing two or more 0s (every position evaluates to 0); Negative numbers flipping product signs; Minimum length array (n = 2). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Product of Array Except Self?
Product of Array Except Self is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Apple.