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, Python, C++ and JavaScript, 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.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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;
}
}class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
out = [0] * n
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j]
out[i] = p
return outclass Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> out(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;
}
};function productExceptSelf(nums) {
const n = nums.length;
const out = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
let p = 1;
for (let 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;
}
}class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
pre, suf, out = [0] * n, [0] * n, [0] * n
pre[0] = 1
for i in range(1, n):
pre[i] = pre[i - 1] * nums[i - 1]
suf[n - 1] = 1
for i in range(n - 2, -1, -1):
suf[i] = suf[i + 1] * nums[i + 1]
for i in range(n):
out[i] = pre[i] * suf[i]
return outclass Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> pre(n), suf(n), out(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;
}
};function productExceptSelf(nums) {
const n = nums.length;
const pre = new Array(n).fill(0), suf = new Array(n).fill(0), out = new Array(n).fill(0);
pre[0] = 1;
for (let i = 1; i < n; i++) pre[i] = pre[i - 1] * nums[i - 1];
suf[n - 1] = 1;
for (let i = n - 2; i >= 0; i--) suf[i] = suf[i + 1] * nums[i + 1];
for (let 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;
}
}class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
out = [0] * n
out[0] = 1
for i in range(1, n):
out[i] = out[i - 1] * nums[i - 1]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return outclass Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> out(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;
}
};function productExceptSelf(nums) {
const n = nums.length;
const out = new Array(n).fill(0);
out[0] = 1;
for (let i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
let right = 1;
for (let 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, Next Permutation, Buildings With an Ocean View.
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.