visual walkthrough
Product of Array Except Self
Prefix/suffix passes without division; a very frequent Amazon and Meta question.
The idea
The product of everything except nums[i] is the product of everything to its left times the product of everything to its right. Both can be built incrementally.
Sweep left to right storing the running left product, then sweep right to left multiplying in the running right product.
Complexity
| approach | time | space |
|---|---|---|
| Multiply the rest | O(n²) | O(1) |
| Prefix and suffix | O(n) | O(1) |