Product of Array Except Self

1. Problem & Core Objective

The problem

Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i].

Input:  nums = [1, 2, 3, 4]        Output: [24, 12, 8, 6]
Input:  nums = [-1, 1, 0, -3, 3]   Output: [0, 0, 9, 0, 0]

Constraints:

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix is guaranteed to fit in a 32-bit integer
• You must write an algorithm that runs in O(n) time and without using the division operation.

Follow-up: can you solve it in O(1) extra space? (The output array does not count.)

What the interviewer is actually testing

The problem hands you two artificial-looking restrictions. Both are deliberate:

1. "Without division" blocks the one-line answer (total / nums[i]), forcing you to find the real structure. It also dodges the division-by-zero problem, which is the hint about what that structure is.
2. "O(n) time" blocks the nested loop.
3. The O(1)-space follow-up is the actual difficulty. Getting to O(n) time with two extra arrays is the expected first answer; folding them away is the differentiator.

What's really being assessed: can you decompose a quantity into independent left and right halves? That's a pattern (prefix/suffix accumulation) that recurs throughout DP and array problems.

2. First-Principles Thought Process

Step 1 — The forbidden solution, and why it's forbidden

The instinct is obvious:

int total = product of everything;
answer[i] = total / nums[i];

O(n), trivial — and banned. But work out why it's a bad idea even without the ban:

Zeros break it. If nums[i] == 0 you'd divide by zero. If there are two or more zeros, every answer is 0. If there's exactly one zero, only that position is non-zero.

Handling that needs zero-counting special cases. The division ban isn't arbitrary — it's steering you away from a solution that's fragile anyway. Say this out loud; it shows you understand the constraint rather than resenting it.

Step 2 — Brute force, and its waste

for (int i = 0; i < n; i++) {
    int prod = 1;
    for (int j = 0; j < n; j++) if (j != i) prod *= nums[j];
    answer[i] = prod;
}

O(n²). Too slow at n = 10^5.

Where's the waste? Computing answer[0] multiplies nums[1] * nums[2] * nums[3]. Computing answer[1] multiplies nums[0] * nums[2] * nums[3]. The sub-product nums[2] * nums[3] is recomputed every single time. Massive overlap.

Step 3 — The decomposition

Look at what "everything except nums[i]" actually means positionally:

nums = [1,  2,  3,  4]
             ↑
         answer[1] = (1) × (3 × 4)
                      └┬┘   └──┬──┘
                    left of 1  right of 1

answer[i] = (product of everything to the LEFT of i) × (product of everything to the RIGHT of i)

That's the whole insight. The element itself is excluded because neither side includes it.

Step 4 — Both halves are cheap to precompute

"Product of everything to the left of i" for all i is a running product, computable in one forward pass:

prefix[0] = 1                         (nothing to the left of index 0)
prefix[i] = prefix[i-1] * nums[i-1]

Symmetrically for the right, in one backward pass. Then answer[i] = prefix[i] * suffix[i].

Three passes, O(n) time, O(n) extra space for the two arrays.

Why prefix[0] = 1 and not 0: the identity for multiplication is 1. "The product of no numbers" is 1, just as "the sum of no numbers" is 0. Getting this wrong zeroes the entire answer.

Step 5 — Fold away the extra space

Two observations collapse the space to O(1):

1. The output array doesn't count as extra space (the problem says so). So compute the prefix products directly into answer.
2. The suffix doesn't need an array. You only ever use suffix[i] at the moment you're processing index i. So carry it in a single variable, updated as you walk backwards.

Two passes, one output array, one scalar.

3. Solution Paths

Approach 1 — Brute force

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

• Time: O(n²).
• Space: O(1) extra.

Name it, state the complexity, explain the overlapping sub-products, move on.

Counter-questions on this approach

⭐ "That's O(n²). Where exactly is the repeated work?"

Computing answer[0] multiplies nums[1] × nums[2] × nums[3]; computing answer[1] multiplies nums[0] × nums[2] × nums[3]. The sub-product nums[2] × nums[3] is recalculated for every index. The overlap between adjacent answers is almost total, which is the signal to precompute.

Approach 2 — Division (banned, but discuss it)

public int[] productExceptSelf(int[] nums) {
    int total = 1, zeros = 0;
    for (int x : nums) {
        if (x == 0) zeros++;
        else total *= x;
    }

    int[] answer = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        if (zeros == 0)                 answer[i] = total / nums[i];
        else if (zeros == 1 && nums[i] == 0) answer[i] = total;   // only this slot survives
        else                             answer[i] = 0;
    }
    return answer;
}

• Time: O(n). Space: O(1).

Banned by the problem, but worth walking through in ten seconds because it demonstrates you understand why it's banned: the three-way zero case is exactly the fragility the restriction removes.

Counter-questions on this approach

⭐ "Why do you think the problem bans division?"

Partly to block the trivial answer, but mainly because it's fragile. Division forces three separate cases: no zeros (divide normally), exactly one zero (only that index is non-zero), and two or more zeros (everything is zero). The restriction steers you toward a formulation that handles zeros with no branches at all.

"If division were permitted, would you use it?"

It's the same O(n) time and O(1) space, so there's no complexity argument either way. I'd still prefer the prefix/suffix version — three zero-branches is three chances to get it wrong, and the branch-free version is easier to verify.

Approach 3 — Prefix and suffix arrays

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n];
    int[] suffix = new int[n];
    int[] answer = new int[n];

    prefix[0] = 1;                                     // nothing to the left of index 0
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] * nums[i - 1];

    suffix[n - 1] = 1;                                 // nothing to the right of the last index
    for (int i = n - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];

    for (int i = 0; i < n; i++) answer[i] = prefix[i] * suffix[i];

    return answer;
}

Trace on nums = [1, 2, 3, 4]:

✓ Matches the expected output.

Read one column to see it working: at i = 2, left is 1×2 = 2, right is 4, product 8 — which is 1×2×4, everything but nums[2] = 3.

• Time: O(n) — three linear passes.
• Space: O(n) extra for the two arrays.

This is a complete, correct answer. Present it first — it makes the decomposition visible. Then offer the optimization.

Counter-questions on this approach

⭐ "You're using O(n) extra space. Can you do better?"

Yes. Two observations collapse it: the output array doesn't count as auxiliary space, so I can write the prefix products directly into it; and the suffix is only ever consumed at the exact index I'm processing, so it can be a single rolling variable instead of an array. That's the next approach.

"Why is prefix[0] = 1 rather than 0?"

1 is the multiplicative identity — "the product of no numbers" is 1, just as "the sum of no numbers" is 0. Initializing it to 0 would zero out the entire result, and it's the most common bug in this problem.

Approach 4 — O(1) extra space (optimal)

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];

    // Pass 1: answer[i] = product of everything to the LEFT of i
    answer[0] = 1;
    for (int i = 1; i < n; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // Pass 2: multiply in the product of everything to the RIGHT, carried in one variable
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];          // extend the suffix to include nums[i] for the NEXT iteration
    }

    return answer;
}

How it works. Pass 1 fills answer with prefix products. Pass 2 walks backwards, multiplying each slot by the running suffix, then extending that suffix.

The ordering inside pass 2 is critical. answer[i] *= suffix must come before suffix *= nums[i], because the suffix for position i must exclude nums[i]. Swap the two lines and every answer includes its own element.

Trace on nums = [1, 2, 3, 4]:

After pass 1: answer = [1, 1, 2, 6]

Result: [24, 12, 8, 6] ✓

Trace with zeros, nums = [-1, 1, 0, -3, 3]:

After pass 1 (prefix): [1, -1, -1, 0, 0]

Result: [0, 0, 9, 0, 0] ✓ — zeros are handled with no special case at all, because a zero simply propagates through the products naturally.

• Time: O(n) — two passes.
• Space: O(1) extra — the output array is required by the problem and excluded by convention; suffix is a single variable.

Counter-questions on this approach

⭐ "You claim O(1) space, but you return an array of size n."

The output is required — I have to return n values, so that allocation is unavoidable, and the problem states explicitly that it doesn't count. The convention is to measure auxiliary space. Beyond the output I use one scalar. I'd phrase it as "O(1) extra space, not counting the output" rather than a bare O(1).

⭐ "What breaks if you swap the two lines inside the backward pass?"

Every answer would wrongly include its own element. answer[i] *= suffix must run before suffix *= nums[i], because the suffix for position i must exclude nums[i]. Swapping them folds each element into its own product.

"Is it actually safe to read and write the same array in the second pass?"

Yes, and it's worth verifying rather than assuming. Each step reads answer[i] and writes answer[i] — the same index, in the same step. There's no cross-index dependency, so no value is clobbered before it's used.

"Can you do it in a single pass?"

No, and the reason is structural rather than a lack of cleverness: answer[0] depends on nums[n-1], so no final value can be emitted before the whole array has been read. Two passes is a genuine lower bound here.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force recomputes overlapping sub-products — nums[2] * nums[3] is recalculated for every i. The prefix/suffix approach computes each partial product once and reuses it. This is the same "cache what you recompute" move as Two Sum, applied to arithmetic rather than lookup.

Against division. Division is O(n) too, so this isn't about speed — it's about robustness. The division solution needs three branches for zero cases. The prefix/suffix solution has no branches at all: a zero just flows through the multiplication and produces the right answer automatically. Fewer special cases means fewer bugs.

Against the two-array version. Same complexity, but the observation that the suffix is only needed at the moment you use it removes an entire array. This is a general technique:

If a precomputed array is consumed in the same order it's produced, you can replace it with a single rolling variable.

That's exactly the "rolling array" space optimization in dynamic programming (19).

Why O(n) time is the floor. Every element affects every other answer, so all n must be read. And you must write n outputs. So O(n) is optimal.

On the space claim — be precise. The output array is O(n), and you cannot avoid that: the problem requires returning n values. The convention is to measure auxiliary space, excluding required output. Say it explicitly:

"O(1) extra space, not counting the output array — which the problem says doesn't count, and which is unavoidable since I have to return n values."

Stating the caveat rather than glossing it is the senior-sounding move.

5. Java Prerequisites

Arrays are zero-initialized

int[] answer = new int[n];        // all zeros, guaranteed

Which is why answer[0] = 1 must be set explicitly — the multiplicative identity is 1, not 0. Forgetting this line zeroes the entire output, and it's the most common bug in this problem.

Backward iteration

for (int i = n - 1; i >= 0; i--) { ... }

Start at the last valid index n - 1, and use >= 0 so index 0 is included. Off-by-ones here are easy — i > 0 would silently skip the first element.

Compound assignment

answer[i] *= suffix;       // equivalent to: answer[i] = answer[i] * suffix

Concise and, importantly, it reads the array slot only once.

Overflow — why it's safe here

-30 <= nums[i] <= 30,  and prefix/suffix products fit in a 32-bit int (per the constraints)

The problem guarantees intermediate products fit. Without that guarantee, 30^100000 would overflow catastrophically and you'd need long or BigInteger.

Raise this unprompted: "The constraints guarantee prefix and suffix products fit in an int, so I don't need long. If they didn't, I'd widen to long — or note that the true product could exceed even that and need BigInteger."

See 03 on overflow.

Reusing the output array

Writing prefix products into answer and then multiplying in place is safe because pass 2 reads and writes the same index in the same step — no cross-index dependency. Worth verifying explicitly before claiming it, since in-place tricks are where subtle bugs live.

6. Interview Communication Guide

Clarifying questions

1. "Can I use division?" — the problem forbids it, but asking shows you spotted the trivial solution.
2. "Does the output array count toward the space complexity?" — conventionally no; confirming makes your O(1) claim precise.
3. "Can the array contain zeros?" — yes, and it's the case that breaks division.
4. "Are overflow guarantees given?" — the constraints say yes; without them you'd need long.
5. "Can I modify the input array?" — not needed here, but good habit.

The pitch

"The obvious solution is to compute the total product and divide by each element — but that's banned, and it'd also need special handling for zeros anyway.

Brute force is a nested loop at O(n²), and it recomputes the same sub-products repeatedly.

The key observation: answer[i] is (everything to the left of i) × (everything to the right of i). Both of those are running products, so I can precompute all the left-products in one forward pass and all the right-products in one backward pass. Three passes, O(n) time, O(n) space.

Then I can fold that to O(1) extra space. I write the prefix products straight into the output array, then walk backwards carrying the suffix in a single variable — because I only need the suffix for position i at the exact moment I'm at i.

The ordering in that second pass matters: multiply into answer[i] before extending the suffix with nums[i], so the suffix never includes the element itself.

O(n) time, O(1) extra space, and zeros need no special case."

Edge cases to raise proactively

The zero cases are the ones to volunteer. "Notice zeros need no special handling here — a zero just propagates through the products. That's exactly what the division approach couldn't do cleanly, which is why the restriction exists."

Trace [1,2,0,4] briefly if asked: prefix [1,1,2,0], suffix [0,0,4,1], product [0,0,8,0]. The only surviving answer is at the zero's own index — correct, since every other position has the zero on one side.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the products could overflow?"

Widen to long, which handles far more. If even that overflows, either use BigInteger (slow but exact) or return results modulo some M — though note that "product except self" modulo M can't use modular division unless M is prime and no element is divisible by it, so you'd keep the prefix/suffix approach and take the modulus at each step.

"What about sum except self, instead of product?"

Much easier — total - nums[i], since subtraction has no zero problem. The prefix/suffix structure still works but is unnecessary. Good contrast for showing why products are harder.

"What if you need it for a 2-D grid — product of all cells except this one?"

Same decomposition, extended: precompute row products and column products, and combine. Or, since there's no division constraint implied, compute the total and handle zeros by counting them.

"Range product queries — product of any subarray [i, j]?"

Prefix products let you answer in O(1) if you can divide (prefix[j+1] / prefix[i]) and there are no zeros. Without division, use a segment tree for O(log n) per query. That's the natural escalation of the prefix-array idea.