March 24
Product of Array Except Self
How to use prefix and suffix products to build the local answer for each index from the surrounding context.
Arrays and Prefix/Suffix Intermediate 20 min TypeScript
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all elements of nums except nums[i].
You must do this without using division.
Example:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
What to notice before coding
- Each position depends on everything except the current value.
- The no-division restriction is the center of the problem.
- The product you need can be split into left and right parts.
Common mistakes
- trying to use division anyway and getting trapped by zeros
- building the prefix correctly but forgetting to combine it with the suffix
Step 1 — See the forbidden shortcut
Without the restriction, the obvious idea would be:
- compute the total product
- divide by
nums[i]
The problem forbids that.
And that makes sense. Zero complicates everything, and the exercise wants a different kind of reasoning.
Step 2 — Ask where the answer for each index comes from
For answer[i], you need the product of:
- everything before
i - everything after
i
That suggests splitting the information in two parts.
Step 3 — Build prefixes
If answer[i] starts by storing the product to the left:
answer[0] = 1answer[1] = nums[0]answer[2] = nums[0] * nums[1]
then half of the answer is already done.
Step 4 — Multiply by suffixes
Then make a right-to-left pass:
- keep a running product from the right
- multiply that into
answer[i]
That makes each position become:
leftPrefix * rightSuffix
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function productExceptSelf(nums: number[]): number[] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Recalculate for each index
Correct, but too slow.
export function productExceptSelf(nums: number[]): number[] {
const answer: number[] = []
for (let index = 0; index < nums.length; index += 1) {
let product = 1
for (let other = 0; other < nums.length; other += 1) {
if (other !== index) {
product *= nums[other]
}
}
answer.push(product)
}
return answer
}Solution 2 — Prefix + suffix accumulators in O(n)
Now each pass accumulates half of the information.
export function productExceptSelf(nums: number[]): number[] {
const answer = new Array(nums.length).fill(1)
let prefix = 1
for (let index = 0; index < nums.length; index += 1) {
answer[index] = prefix
prefix *= nums[index]
}
let suffix = 1
for (let index = nums.length - 1; index >= 0; index -= 1) {
answer[index] *= suffix
suffix *= nums[index]
}
return answer
}Each index receives the left product in one pass and the right product in the other.
What to say in the interview
A strong short explanation would be:
Without division, each answer should be thought of as product of the left side times product of the right side. I make one pass storing prefixes in the result array, then another pass multiplying by running suffixes. That keeps the solution
O(n)without recomputing everything for each index.
That shows that you:
- understood why division was forbidden
- broke the problem into reusable parts
- explained prefix/suffix as composition, not a trick
When this pattern shows up again
The same pattern comes back when you need to:
- combine accumulated information from both sides
- answer per index without recomputing everything
- work with
prefix sumsor prefix products - turn a global dependency into two local passes
The point is not memorizing
productExceptSelf.
The point is noticing when the answer can be built from partial accumulators.