Medium
Prefix Sums
Product of Array Except Self
Each answer is the product of everything to its left times everything to its right.
Approach
Without division, build the answer in two sweeps: a left-to-right pass filling each slot with the running prefix product, then a right-to-left pass multiplying in the running suffix product. The output array doubles as scratch space for O(1) extra memory.
Time complexity
O(n)
Space complexity
O(1) extra
Common mistake
Using division to divide the total product by each element — it breaks when the array contains a zero.
See it run, step by step
Generate an interactive lesson for Product of Array Except Self — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Product of Array Except Self