Explain Product of Array Except Self without division.

Short answer: Build prefix products from the left and suffix products from the right. For index i, answer[i] = prefix[i] * suffix[i]. You can do it with one output array and one running suffix to achieve O(1) extra space (excluding output).

Interview approach

1. Clarify: no division; O(n) time expected.
2. First pass: answer[i] = product of all left of i.
3. Second pass from right: multiply by running right product.

Sample solution

int[] ProductExceptSelf(int[] nums) {
    int n = nums.Length;
    var ans = new int[n];
    ans[0] = 1;
    for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * nums[i - 1];
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

Complexity

Time O(n), Space O(1) extra (output not counted).

Edge cases to mention

• Zeros in the array (one zero vs two zeros)
• Negatives

Never use division in the interview version — many panels explicitly forbid it.