Challenge: product of array except self
For each position, the product of everything else — in O(n), and without division.
- Build an answer from prefix and suffix passes
- Handle the zero case that rules out the division shortcut
Optional challenge. Two traps are blocked here: the division shortcut is defeated by a test containing a zero, and the O(n²) recompute is rejected by the read-count efficiency check. You'll need the real O(n) idea.
Return a list where each position holds the product of all the other numbers.
For [1, 2, 3, 4] the answer is [24, 12, 8, 6].
The tempting shortcut — multiply everything, then divide out each element — breaks
the moment there's a 0 in the list (division by zero), and it's banned for that
reason. Recomputing each product from scratch is O(n²). The clean O(n) solution
uses two sweeps.
Idea: for each index, the answer is (product of everything to its left) × (product of everything to its right). Do one left-to-right pass filling in the running prefix product, then one right-to-left pass multiplying in the running suffix product. No division, two passes.
Write product_except_self(nums): a list where out[i] is the product of every element except nums[i]. No division. Handle zeros. Aim for O(n).
product_except_self([1, 2, 3, 4]) → [24, 12, 8, 6]product_except_self([1, 2, 0, 4]) → [0, 0, 8, 0]The zero case is the giveaway that division won't save you — prefix/suffix products sidestep it entirely.