Product of Array Except Self: Prefix x Suffix, No Division

• Product of Array Except Self – produces, for each position, the product of every other element without using division.
• Prefix product – a left-to-right sweep fills output[i] with the product of all elements strictly before index i.
• Suffix product – a right-to-left sweep multiplies each output[i] by the product of all elements strictly after index i.
• O(n) time, O(1) extra space – two passes, with the output array holding intermediates and one suffix scalar variable.
• Zero-safe – handles any number of zeros correctly without branching, unlike a division-based approach.

What is the Product of Array Except Self problem?

Given an integer array, produce an output array where each position holds the product of all elements except the one at that position. You must do this without using division and in O(n) time.

For example, given [1, 2, 3, 4], the output is [24, 12, 8, 6].

Why is division forbidden?

Division fails when any element is zero, because you cannot divide by zero. Handling zeros with division turns into an ugly special case: you must count zeros and branch on whether there are zero, one, or more. The prefix-suffix method avoids division entirely and handles zeros naturally.

// Division approach: breaks on zeros
int total = 1;
for (int x : nums) total *= x;
for (int i = 0; i < n; i++) out[i] = total / nums[i]; // DivisionByZero!

How does the two-pass prefix-suffix method work?

Pass 1 (left to right): fill each output position with the product of everything strictly to its left. Keep a running prefix product starting at 1.

Pass 2 (right to left): carry a running suffix product, also starting at 1. Multiply each output slot by the suffix, then update the suffix.

After both passes, each position holds prefix times suffix, which is the product of everything except itself.

Array:    [1,  2,  3,  4]

Pass 1 (prefix):
  out[0] = 1           (nothing to the left)
  out[1] = 1           (prefix *= 1 → prefix=1)
  out[2] = 1*2 = 2     (prefix *= 2 → prefix=2)
  out[3] = 2*3 = 6     (prefix *= 3 → prefix=6)
  Output after pass 1: [1, 1, 2, 6]

Pass 2 (suffix, right to left):
  out[3] = 6 * 1 = 6   (suffix=1, then suffix *= 4 → 4)
  out[2] = 2 * 4 = 8   (suffix=4, then suffix *= 3 → 12)
  out[1] = 1 * 12 = 12 (suffix=12, then suffix *= 2 → 24)
  out[0] = 1 * 24 = 24 (suffix=24)
  Final output: [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 (left to right)
        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 (right to left)
        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[] factors = {
            new BigDecimal("1.05"), new BigDecimal("0.98"),
            new BigDecimal("1.02"), new BigDecimal("1.10")
        };
        BigDecimal[] result = productExceptSelf(factors);
        System.out.println("Except-self products: " + Arrays.toString(result));
    }
}

Except-self products: [1.09956, 1.17810, 1.13190, 1.04958]

How does zero handling work for free?

If exactly one element is zero, only that position gets a non-zero answer (the product of all the others), and every other position gets zero because the prefix or suffix passes through zero. If two or more elements are zero, every position's answer is zero. All of this happens naturally without special branches.

// Array: [1, 0, 3, 4]
// Prefix pass: [1, 1, 0, 0]
// Suffix pass: result = [0, 12, 0, 0]
// Only index 1 is non-zero: 1*12 = 12 = 1*3*4

What about space complexity?

Using the output array to hold prefix intermediates and a single suffix scalar means no separate suffix array is needed. Extra space is O(1) beyond the required output. The problem usually says the output does not count toward extra space, so this is optimal.

How is this related to prefix sums?

This is the multiplication analog of prefix sums. Where prefix sums precompute running totals for range-sum queries, prefix products precompute running products for except-self queries. The pattern is the same: precompute from one direction, combine with a sweep from the other.

| Technique | Operation | Use case |
|---|---|---|
| Prefix sum | Addition | Range sum queries |
| Prefix product | Multiplication | Except-self product |
| Prefix XOR | XOR | Find missing number |

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.
• All zeros – every position is zero.
• One zero – only the zero's position is non-zero.
• Large values – use BigDecimal to avoid overflow.

What should a senior engineer know?

For genuine financial products like compounded interest multipliers or risk weights, always use BigDecimal with its multiply method to stay exact. Primitive int or long products overflow quickly with even modest array sizes. This is the same approach used in sensitivity analysis to compute leave-one-out effects.

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 output array for the prefix pass.
• What if there are zeros? – Handled naturally.
• What about overflow? – Use BigDecimal or long depending on constraints.