A catalog job stores a per-SKU scale factor. Downstream wants, for each SKU, the product of every other factor — the one you are looking at is left out so a later multiply can put it back. The first version nested a scan: for each i, multiply every j != i. A few hundred SKUs finished before breakfast. A few hundred thousand SKUs were still multiplying when the warehouse cutoff passed.

The intern shortcut was a total product divided by nums[i]. Then a SKU with factor 0 landed in staging. Division by zero. After a special-case for one zero, two zeros made every other slot wrong anyway.

Each index wants the product of everyone else. An array already gives nums[i] for free. Nested multiply uses that and still pays O(n²). Division looks linear until a zero shows up. The prefix sum post owns range sums and exclusive versus inclusive tables. Here the aggregate is a product, and we never ask for an interior slice — we ask for everything except one index.

The problem

Given an int[] nums, return an int[] answer the same length such that answer[i] is the product of every nums[j] with j != i. Do not use division. Linear time is the bar.

nums = [1, 2, 3, 4]  →  [24, 12, 8, 6]
nums = [2, 0, 3]     →  [0, 6, 0]
nums = [0, 0, 4]     →  [0, 0, 0]

Note: One zero means every other answer[i] is 0, and the zero’s own slot is the product of the rest. Two or more zeros mean the whole answer is 0. Division cannot express either case without a separate zero-count, which is why interviews ban it: they want the prefix/suffix walk, not a total-and-divide plus a trap door.

Nested multiply is the honest brute force

Every index multiplies the rest. Correct. Quadratic.

int[] productExceptSelfNested(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    for (int i = 0; i < n; i++) {
        int p = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) {
                p *= nums[j];
            }
        }
        answer[i] = p;
    }
    return answer;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested product for a question two linear passes answer: left of i times right of i. The honest middle step is two extra arrays: left[i] is the product of everything strictly left of i, right[i] everything strictly right, then answer[i] = left[i] * right[i]. Same idea, O(n) extra besides the output.

Left products into the output, then a running right

You do not need those two arrays. The output already has a slot per index.

First pass, left to right: write into answer[i] the product of everything strictly before i. answer[0] is 1 — the empty product. Second pass, right to left: keep a running right (starts at 1). Multiply answer[i] by right, then fold nums[i] into right. After that, answer[i] holds left-of-i times right-of-i.

Walk [1, 2, 3, 4]:

after left pass:  answer = [1, 1, 2, 6]
                  empty, 1, 1*2, 1*2*3

right starts at 1
i=3  answer[3] *= 1   → 6    right *= 4 → 4
i=2  answer[2] *= 4   → 8    right *= 3 → 12
i=1  answer[1] *= 12  → 12   right *= 2 → 24
i=0  answer[0] *= 24  → 24   right *= 1 → 24

answer = [24, 12, 8, 6]

The Java is those two passes:

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    answer[0] = 1;
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= right;
        right *= nums[i];
    }
    return answer;
}

Time is O(n) — two linear passes. Extra space is O(1) besides the output; the output is required, so it does not count against the extra budget. The two-array version is the same time and easier to explain; the in-output version is what they want when they say “constant extra space.”

Note: Division by the total product fails on a zero. One zero is a special case. Two zeros are another. Prefix and suffix products do not care.

What interviewers usually poke next

  • Two extra arrays vs in-output. left[] and right[] are legal if extra O(n) is allowed. Say you would collapse them into answer when they tighten the space bill.
  • If division were allowed. Total product over nums[i] works only with no zeros. Count zeros: none → divide; one → only that index is the product of the rest; two or more → all zeros. Then say why they still asked you not to.
  • Overflow. int multiply wraps in Java. If the products will not fit, switch the output (and right) to long[] and name that.
  • Empty or single element. The prompt usually promises n >= 2. Empty is an empty answer; one element is [1] (the empty product). At the board, ask.

You are done with this problem when you can fill [1, 2, 3, 4] on a whiteboard in two passes, and you can say out loud why a zero makes division the wrong tool.