Compute product excluding index without division

Given an integer array nums, return an array ans where ans[i] equals the product of all elements of nums except nums[i], without using division. Achieve O(n) time and O(1) extra space beyond the output array. Perform a step-by-step dry run showing how prefix and postfix accumulators update at each index. Explain how your solution handles zeros and negative numbers and how you would mitigate overflow in languages with fixed-width integers.

Product of Array Except Self (No Division)

Given an integer array nums, return an array ans where ans[i] equals the product of every element of nums except nums[i]. You may NOT use the division operator.

Solve it in O(n) time and O(1) extra space, not counting the output array itself.

Approach (prefix/postfix accumulators):

1. First left-to-right pass: ans[i] holds the product of all elements strictly to the left of i (a running prefix, starting at 1).
2. Second right-to-left pass: multiply ans[i] by a running postfix of all elements strictly to the right of i (starting at 1).
3. After both passes ans[i] = prefix(i) * postfix(i) = product of everything except nums[i].

Dry run on [1,2,3,4] — prefix pass: ans=[1,1,2,6] (prefix updates 1→1→2→6→24). Postfix pass (right to left): i=3 ans[3]=1→6, postfix=4; i=2 ans[2]=4→8, postfix=12; i=1 ans[1]=12→12, postfix=24; i=0 ans[0]=24→24, postfix=24. Result [24,12,8,6].

Zeros: With one zero, only that index gets the product of the others; all other indices become 0. With two or more zeros, every output is 0 — the prefix/postfix method handles this automatically because the zero zeroes out every accumulator that crosses it. Negatives: sign is preserved naturally by multiplication; no special handling needed. Overflow: in fixed-width-integer languages the full product can exceed the type range; the problem guarantees the answer fits in 32-bit, but use a 64-bit accumulator (long / int64) for the intermediate prefix/postfix to stay safe.

Constraints

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
• You must NOT use the division operator
• O(n) time; O(1) extra space not counting the output array

Examples

Example 1

Input: ([1, 2, 3, 4],)
Output: [24, 12, 8, 6]

Explanation: ans[0]=234=24, ans[1]=134=12, ans[2]=124=8, ans[3]=123=6.

Example 2

Input: ([-1, 1, 0, -3, 3],)
Output: [0, 0, 9, 0, 0]

Explanation: Exactly one zero (at index 2): every other index includes that zero in its product and becomes 0; index 2 gets (-1)1(-3)*3 = 9.

Hints

1. ans[i] = (product of everything to the LEFT of i) * (product of everything to the RIGHT of i). Compute each side with a single linear pass.
2. Reuse the output array as scratch: first store the left/prefix products, then multiply in the right/postfix products on a second pass — that keeps extra space O(1).
3. Carry one running accumulator per direction, initialized to 1. Multiply it by nums[i] AFTER writing it into ans[i] so the current element is excluded. Use a 64-bit accumulator to avoid intermediate overflow.