Topic · Prefix SumMedium
Product of Array Except Self
Understand the problem
Given an integer array nums, return an array result where result[i] equals the product of all the elements except nums[i].
Key constraints: you may not use division, and the algorithm must run in O(n).
Example:
ts
nums = [1, 2, 3, 4]
output = [24, 12, 8, 6]
// result[0] = 2·3·4 = 24, result[1] = 1·3·4 = 12, ...Division is banned for a practical reason: the array can contain zeros, and dividing by zero is undefined.
This problem applies the prefix idea, but with multiplication instead of addition.
Basic approach
O(n²) time, O(1) extra space (not counting the output array)ts
function productExceptSelf(nums: number[]): number[] {
const n = nums.length
const result: number[] = []
for (let i = 0; i < n; i++) {
let product = 1
// multiply all elements except index i
for (let j = 0; j < n; j++) {
if (j !== i) product *= nums[j]
}
result.push(product)
}
return result
}Why this approach is slow:
For each index i you rescan the whole array to multiply the other n−1 elements.
Two nested loops → O(n²), too slow when n is around 10⁵.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.