Day 25/75: Product of Array Except Self
75 Day DSA in Python Challenge
I shipped a revenue dashboard tile that, for each product, displayed the combined value of every other product's price. The intent was to answer a business question: if any single SKU disappeared, how much of the day's revenue is still accounted for by the rest? So for each item I needed the product of all the other items, excluding itself.
The version that broke
My first implementation was the arithmetic shortcut everyone reaches for. Multiply every price into one grand total, then divide that total by each item's own price to get the product of everything else.
def share_naive(prices): grand = 1 for p in prices: grand *= p return [grand // p for p in prices] # breaks the instant any p is 0 It passed every test I wrote, because every test used positive prices. Then a clearance SKU was marked down to a price of zero. The grand product collapsed to zero, every division produced a wrong zero, and the division by the zero item itself raised ZeroDivisionError. Division had silently assumed every value was invertible, and one free promo item violated that assumption for the entire catalog.
Why LeetCode 238 forbids division
This is exactly Product of Array Except Self, LeetCode 238, and the problem states its constraint outright: solve it without division, in O(n). I used to read that as an arbitrary interview handicap. After this bug, I read it as a correctness requirement. Division forces you to invert each element, and zero has no inverse. Even ignoring zeros, repeatedly dividing floating-point numbers accumulates rounding error in a way that repeated multiplication of the same operands does not. The no-division rule is protecting you from the failure I shipped.
The reframe
Stop thinking about a grand total. For any index i, the answer is the product of everything to its left times the product of everything to its right. Neither piece includes the element itself, so its value, zero or not, never enters its own answer.
def product_except_self(stock): n = len(stock) out = [1] * n left = 1 for i in range(n): out[i] = left # everything strictly left of i left *= stock[i] # fold i in for the next index right = 1 for i in range(n - 1, -1, -1): out[i] *= right # multiply in everything strictly right of i right *= stock[i] return out inventory = [6, 0, 3, 2] # index 1 is the free promo SKU print(product_except_self(inventory)) # [0, 36, 0, 0] The ordering inside each loop
The single detail that makes or breaks this: in the left pass, I assign out[i] = left before I multiply stock[i] into left. That ordering guarantees left holds the product of everything strictly before i and never includes the current element. Update first and assign second, and every answer wrongly includes its own value, which is precisely what the problem forbids. The right pass mirrors the same discipline.
Tracing the zero case
For the free SKU at index 1, its left product is 6 and its right product is 3 * 2 = 6, so its answer is 36, the correct product of all its non-zero neighbors. For every other index, either the left sweep or the right sweep crosses the zero, so the answer is correctly zero. The zero is now just another factor, never a divisor.
Complexity
- Time: two linear sweeps, each O(n), so O(n) overall instead of the O(n^2) nested all-pairs version.
- Space: reuse the output array for the left products and carry the right product in a single scalar, so O(1) extra space. The returned array is required output, not auxiliary scratch, so claiming O(1) extra is honest.
The edge case that comes for free
Two or more zeros in the array make every answer zero, because each index then has at least one zero either to its left or its right. The prefix-suffix method handles this with no special code. The division approach would have needed an explicit count-the-zeros branch, which is more code and more places to be wrong.
What I'm taking away
The Friday failure was not a bug in a loop. It was choosing a tool, division, whose precondition (every value is invertible) my data violated the moment a price hit zero. Reframing the answer as left product times right product removed the precondition entirely.
When a problem tempts you to divide by an element, do you reach for prefix and suffix products, or do you special-case the zeros? Which reads cleaner to you, and have you hit a real-world version of this bug?
