Product of Array Except Self
Product of Array Except Self is a medium arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (output array + right-to-left pass), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, from brute force up.
Problem
Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].
Do it in O(n) time without using division.
Examples
Example 1
- Input
nums = [2, 3, 4, 5]- Output
[60, 40, 30, 24]
Example 2
- Input
nums = [-1, 2, 0, 3]- Output
[0, 0, -6, 0]- Why
- Only the position of the zero gets a non-zero product.
Constraints
2 <= nums.length <= 10^5- Every prefix and suffix product fits in a 32-bit integer.
- Do not use division.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Better (prefix and suffix arrays) | O(n) | O(n) |
| Optimal (output array + right-to-left pass) | O(n) | O(1) |
1Brute force
O(n²)O(1)Besides the output array.For each index, multiply every other element.
- For each i, loop over j != i and multiply.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] out = new int[n];
for (int i = 0; i < n; i++) {
int p = 1;
for (int j = 0; j < n; j++) if (j != i) p *= nums[j];
out[i] = p;
}
return out;
}
}2Better (prefix and suffix arrays)
O(n)O(n)Precompute prefix[i] = product of nums[0..i-1] and suffix[i] = product of nums[i+1..n-1], then multiply them.
- Fill prefix left to right, suffix right to left.
- out[i] = prefix[i] * suffix[i].
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] pre = new int[n], suf = new int[n], out = new int[n];
pre[0] = 1;
for (int i = 1; i < n; i++) pre[i] = pre[i - 1] * nums[i - 1];
suf[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) suf[i] = suf[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++) out[i] = pre[i] * suf[i];
return out;
}
}3Optimal (output array + right-to-left pass)
O(n)O(1)The output array does not count as extra space.Store prefix products directly in the output array, then walk from the right keeping the suffix product in one variable and multiply it in.
- out[i] = product of everything left of i.
- right = 1; for i from n - 1 down: out[i] *= right; right *= nums[i].
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] out = new int[n];
out[0] = 1;
for (int i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
int right = 1;
for (int i = n - 1; i >= 0; i--) {
out[i] *= right;
right *= nums[i];
}
return out;
}
}Edge cases to test
- One zero in the array
- Two or more zeros (every answer is 0)
- Negative numbers
Hints
Hint 1
answer[i] = (product of everything left of i) × (product of everything right of i).
Hint 2
Can the output array hold the left products while a single variable carries the right product?
FAQ
What is the best time complexity for Product of Array Except Self?
Optimal (output array + right-to-left pass) runs in O(n) time and O(1) extra space.
Which pattern does Product of Array Except Self use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders.
Is there a brute force solution for Product of Array Except Self?
Yes. Brute force takes O(n²) time and O(1) space. For each index, multiply every other element.
Which edge cases should I test for Product of Array Except Self?
One zero in the array; Two or more zeros (every answer is 0); Negative numbers.