Product of Array Except Self
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Walmart
Problem
Given an integer array nums, return an array answer such that answer[i] is the product of all the elements of nums except nums[i]. You must solve it without using division and in O(n) time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Uber | Medium | View all Uber questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
The product of all except nums[i] = (product of all to the left of i) × (product of all to the right of i).
First pass (left to right): result[i] = product of all elements to the left of i. This is a prefix product.
Second pass (right to left): multiply result[i] by the product of all elements to the right of i. This is a suffix product.
You can do it in one output array by using the result array for prefix products, then a running suffix variable for the second pass.
Why no division: division by zero is undefined, and the problem explicitly forbids it. The two-pass approach avoids division entirely.
Visual walkthrough for [1,2,3,4]:
Pass 1 (prefix): result = [1, 1, 2, 6]
result[0]=1 (nothing left), result[1]=1 (left of 1), result[2]=1×2=2, result[3]=1×2×3=6
Pass 2 (suffix): suffix=1
i=3: result[3]=6×1=6, suffix=4
i=2: result[2]=2×4=8, suffix=12
i=1: result[1]=1×12=12, suffix=24
i=0: result[0]=1×24=24, suffix=24
Result: [24,12,8,6]
Edge cases: single element (return [1]), zero in array (still works since we don't divide).
Optimal Approach
Step 1: Create result array of size n, fill with 1.
Step 2: Left pass — prefix = 1. For i from 0 to n-1:
result[i] = prefix
prefix *= nums[i]
Step 3: Right pass — suffix = 1. For i from n-1 down to 0:
result[i] *= suffix
suffix *= nums[i]
Step 4: Return result.
The left pass stores the product of everything to the left. The right pass multiplies by the product of everything to the right.
Time: O(n). Space: O(1) extra (output array not counted).
What Trips People Up in Real Interviews
Using division. The problem explicitly forbids it, and it doesn't handle zeros correctly.
Confusing "product of all except self" with "product of all." You need to exclude the current element.
Not handling zeros. If there are two or more zeros, the result is all zeros. If there's one zero, all positions except that one are zero.
Forgetting to initialize the result array to 1, not 0. Multiplying by 0 gives 0.
Using two separate arrays for prefix and suffix products. You can do it in one output array plus a single running variable — no need for extra O(n) space.
Solution Code
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return resultFrequently Asked Questions
What is the Product of Array Except Self problem?
Given an integer array nums, return an array answer such that `answer[i]` is the product of all the elements of nums except `nums[i]`. You must solve it without using division and in `O(n)` time.
How do you solve Product of Array Except Self?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Product of Array Except Self?
Product of Array Except Self is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Walmart. It is a medium difficulty problem.
What are common mistakes on Product of Array Except Self?
- Using division. The problem explicitly forbids it, and it doesn't handle zeros correctly.
- Confusing "product of all except self" with "product of all." You need to exclude the current element.
- Not handling zeros. If there are two or more zeros, the result is all zeros. If there's one zero, all positions except that one are zero.
- Forgetting to initialize the result array to 1, not 0. Multiplying by 0 gives 0.
- Using two separate arrays for prefix and suffix products. You can do it in one output array plus a single running variable — no need for extra `O(n)` space.