Product of Array Except Self
Product of Array Except Self is a medium Arrays & Hashing problem from the Blind 75. The key pattern is prefix and suffix products, and a good solution runs in O(n) time.
Problem
For each position, return the product of every array value except the value at that position, without division.
Examples
Example 1
Input
[2,3,4,5]Output
[60,40,30,24]Example 2
Input
[1,2,3]Output
[6,3,2]Example 3
Input
[0,4,0]Output
[0,0,0]Approach
Fill the answer with products of everything to the left, then sweep from the right with a running product of everything to the right.
| Pattern | Prefix and suffix products |
|---|---|
| Time | O(n) |
| Space | O(1) beyond the output |
Watch out for
Division is not allowed, and zeros make it wrong anyway; the two sweeps handle zeros naturally.