Product of Array Except Self: Prefix Product Times Suffix Product

• Product of Array Except Self – for each index, compute the product of all other elements without division, in O(n) time.
• Prefix product pass – left-to-right: result[i] = product of all elements before index i.
• Suffix product pass – right-to-left: multiply each result[i] by the product of all elements after index i.
• O(n) time, O(1) extra space – the result array stores intermediates; one suffix scalar is the only extra variable.
• Zero-safe – zeros are handled naturally with no special branches.

What is the Product of Array Except Self problem?

Given an integer array, return an array where each position holds the product of all elements except the one at that index. You must do it without division and in O(n) time. For example, [1, 2, 3, 4] produces [24, 12, 8, 6].

Why is division forbidden?

Division fails when any element is zero (division by zero), and handling zeros requires ugly branching: count zeros, branch on zero/one/many. The prefix-suffix approach sidesteps all of this.

How does the two-pass method work?

Pass 1 (left to right): fill each slot with the product of everything strictly to its left, using a running prefix product starting at 1.

Pass 2 (right to left): carry a running suffix product (starting at 1), multiply it into each slot, then update the suffix.

Array:    [1,  2,  3,  4]

Pass 1 (prefix):
  result[0] = 1
  result[1] = 1
  result[2] = 1*2 = 2
  result[3] = 2*3 = 6
  After: [1, 1, 2, 6]

Pass 2 (suffix):
  result[3] = 6*1 = 6,   suffix = 1*4 = 4
  result[2] = 2*4 = 8,   suffix = 4*3 = 12
  result[1] = 1*12 = 12, suffix = 12*2 = 24
  result[0] = 1*24 = 24
  Final: [24, 12, 8, 6]

How do you implement it? (with code)

package com.bank.analysis;

import java.math.BigDecimal;
import java.util.Arrays;

public class ProductExceptSelf {

    public static BigDecimal[] productExceptSelf(BigDecimal[] factors) {
        int n = factors.length;
        BigDecimal[] result = new BigDecimal[n];

        // Pass 1: prefix products
        BigDecimal prefix = BigDecimal.ONE;
        for (int i = 0; i < n; i++) {
            result[i] = prefix;
            prefix = prefix.multiply(factors[i]);
        }

        // Pass 2: multiply in suffix products
        BigDecimal suffix = BigDecimal.ONE;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i].multiply(suffix);
            suffix = suffix.multiply(factors[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        BigDecimal[] growthFactors = {
            new BigDecimal("1.05"), new BigDecimal("0.00"),
            new BigDecimal("1.02"), new BigDecimal("1.10")
        };
        BigDecimal[] result = productExceptSelf(growthFactors);
        System.out.println("Except-self: " + Arrays.toString(result));
    }
}

Except-self: [0.0000, 1.1781, 0.0000, 0.0000]

Note: one zero in the array makes every position zero except the zero's own position.

How does zero handling work for free?

With one zero: the prefix or suffix passing through zero zeroes out every other position, and the zero's position gets the product of all non-zero elements. With two or more zeros: every position is zero. No special branch needed.

What about space complexity?

The result array stores prefix intermediates in pass 1. The suffix is a single scalar. So extra space beyond the required output is O(1), which is the standard convention.

How is this related to prefix sums?

| Technique | Operation | Precompute | Query |
|---|---|---|---|
| Prefix sum | Addition | Running total | Range sum in O(1) |
| Prefix product | Multiplication | Running product | Except-self product |

The structural idea is identical: precompute from one direction, combine with a sweep from the other.

What are the edge cases?

• Array of length 1 – the except-self product is 1 (product of nothing).
• Array of length 2 – each element's answer is the other element.
• One zero – only the zero's position is non-zero.
• All zeros – every position is zero.
• Large values – use BigDecimal to avoid overflow.

What are common mistakes?

// Wrong: using division
int total = 1;
for (int x : nums) total *= x;
for (int i = 0; i < n; i++) result[i] = total / nums[i];
// Fails on zero! And violates the no-division constraint.

// Correct: two-pass prefix-suffix
// (as shown above)

What should a senior engineer know?

For financial products like compounded interest multipliers or risk weights, always use BigDecimal. The algorithm is structurally identical with multiply replacing *. This is also used in sensitivity analysis to compute leave-one-out effects without division.

What are common interview follow-up questions?

• Can you do it without division? – Yes, prefix and suffix products.
• Can you do it in O(1) extra space? – Yes, reuse the result array for the prefix pass.
• What about overflow? – Use BigDecimal or long.
• What if there are zeros? – Handled naturally by the two-pass method.