Compute product excluding index without division
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: This question evaluates array-manipulation and algorithmic problem-solving skills, focusing on computing a product-for-each-index using prefix and postfix accumulation concepts while reasoning about edge cases such as zeros, negative numbers, and integer overflow.
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
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Explanation: ans[0]=2*3*4=24, ans[1]=1*3*4=12, ans[2]=1*2*4=8, ans[3]=1*2*3=6.
Input: ([-1, 1, 0, -3, 3],)
Expected 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
- 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.
- 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).
- 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.