Product of Array Except Self
The problem
For each position, return the product of every array element except the one at that position. Use no division and aim for linear time. The array has at least two integers.
Example
[3, 2, 4] → [8, 12, 6]
Need a hint?
Separate the elements before an index from the elements after it.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
In a forward pass, store the product strictly before each index. In a backward pass, multiply that entry by the product strictly after the index. Update each running product only after using it. This naturally handles one or multiple zeros.
Complexity
O(n) time and O(1) extra space excluding the output array.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.