Product of Array Except Self

Problem

Given an integer array, return an array where each element is the product of all other elements in the input. Solve it in O(n) time without using division.

Input: [1, 2, 3, 4]    → [24, 12, 8, 6]
Input: [-1, 1, 0, -3, 3]  → [0, 0, 9, 0, 0]

Solution

Approach - prefix and suffix product passes, reusing the output array.

Each answer is result[i] = (product of everything left of i) * (product of everything right of i). The trick is to build these two halves in two sweeps without ever dividing and without a second array. First pass, left to right: carry a running prefix starting at 1, and before folding nums[i] into it, write the current prefix into result[i]. So after this pass result[i] holds the product of all elements strictly to the left of i (and result[0] is 1, the empty product). Second pass, right to left: carry a running suffix starting at 1, multiply result[i] *= suffix, then fold nums[i] into suffix. Now each slot has been multiplied by the product of everything to its right.

Writing the prefix before updating it (and the suffix likewise) is what keeps element i out of its own product. Trace [1, 2, 3, 4]: after the left pass result = [1, 1, 2, 6]. The right pass with suffix going 1, 4, 12, 24 gives result = [24, 12, 8, 6].

Edge cases - zeros need no special handling: a zero anywhere left or right of i lands in that side's product naturally, so [-1, 1, 0, -3, 3] yields [0, 0, 9, 0, 0] - only index 2 escapes the zero. Avoiding division is also why a zero-containing array doesn't break.

Complexity - O(n) time, O(1) extra space - two linear passes; the output array does not count, and the suffix is a single accumulator.