Product of Array Except Self

Product of array except self returns an array where each position holds the product of every other element. Two constraints shape the solution: division is forbidden, and the output array does not count toward the space complexity. The division ban is not arbitrary. Dividing the total product by each element breaks on zeros, and handling one zero, two zeros, and no zeros separately is exactly the messy case analysis the constraint exists to prevent. The clean approach splits each answer into two halves: - The product of everything except position i is the product of everything to its left times the product of everything to its right. So two passes suffice. The first walks left to right, writing into the output the running product of everything before each position. The second walks right to left, multiplying each entry by the running product of everything after it. The second pass needs only a single variable for the right-hand running product, not another array — which is how the solution reaches O(1) extra space. Both running products start at 1, not 0. Starting at zero makes every result zero, which is the most common bug here. The boundaries handle themselves: position 0 has nothing to its left, and its left product stays at the initial 1, which is correct since an empty product is 1. Zeros need no special handling at all. A single zero makes every other position zero automatically, and two zeros make everything zero — both fall out of the multiplication without a branch. The cost is O(n) time with O(1) extra space, excluding the output as the problem allows.

When each output combines all elements except the current one, look for a left contribution and a right contribution. Prefix and suffix accumulation avoids rebuilding those two ranges for every index and avoids the problems division has with zero.