Product of Array Except Self — Prefix × Suffix, No Division (LeetCode 238)
Try it yourself — the full written explainer and an interactive visualizer are here:
https://unrote.com/problems/product-o...
Product of Array Except Self is a favorite interview question with one sneaky rule: return, for each position, the product of every other number, in O(n) time and without using division. In this video we build the solution from absolute zero, assuming nothing.
We start with the obvious approach, a nested loop that multiplies all the others for each position, and see exactly why it is O(n squared). Then we look at the shortcut everyone reaches for, dividing the total product by each number, and why it fails: a single zero breaks it, and division is banned outright.
The key idea is a clean split: the product of everything except position i is just the product of everything to its left, times the product of everything to its right. That is the multiply-twin of a prefix sum, so we build a running product from each end. One forward pass for the left products, one backward pass for the right, and the answer falls out, slot by slot. We finish with the trick that drops the extra space to O(1) by reusing the output array and carrying a single running value.
Chapters
0:00 Intro
0:23 The problem
0:48 The brute force, and why it is slow
1:12 The division trap
1:36 Why O(n squared) hurts
2:01 The one idea: left times right
2:24 A pattern you know: prefix sums
2:46 Pass one: products from the left
3:19 Pass two: products from the right
3:46 Multiply the two sides
4:15 One array, one variable
4:40 The honest cost
5:01 The shape to remember
5:25 Recap
Read the full written explainer with an interactive visualizer:
https://unrote.com/problems/product-o...
Prerequisite concept, prefix sums:
https://unrote.com/concepts/prefix-sum/
Unrote. Understand it, don't memorize it.
https://unrote.com