product-of-array-except-self

Difficulty: Medium  ·  Topic: Arrays & Hashing  ·  Practice it on parikshan: /practice/product-of-array-except-self/start

The story

A risk engineer at JPMorgan models portfolio exposure across n derivative positions. Each position has a daily P&L multiplier, and the team wants, per position, the "what-if removed" multiplier: if I delete this position, what does the rest of the portfolio multiply out to? They need that answer for every position in a single scan because the dashboard refreshes every second across thousands of portfolios. Division across the array is not an option: a single position with a zero P&L day would crash the calculation, and round-trip floating-point division is not bit-exact when audit-trail integers are required.

That is product-of-array-except-self. It is the prefix-suffix idiom in its purest form: for every index, give me an aggregate of everything to the left and everything to the right, without re-scanning.

What's actually being asked

Given an integer array nums of length n, build an array output such that output[i] is the product of every element of nums except nums[i]. The catch: no division, and the algorithm must run in O(n) time. The output array itself does not count toward extra-space accounting; the optimal solution uses O(1) auxiliary memory.

The naive approach

For each i, multiply the other n - 1 elements from scratch. O(n^2). At n = 10^5, that is 10^10 multiplications. Times out instantly.

The "division trick": compute the total product, then for each i set output[i] = total / nums[i]. O(n). Forbidden by the spec, for two excellent reasons: any zero in the array crashes the calculation, and the audit/integer-precision argument matters in real systems.

The key insight

output[i] is the product of two halves: everything strictly before i, and everything strictly after i. Each half is an associative aggregate, and associative aggregates can be computed in a single sweep.

Two passes are enough:

• Left pass: walk left to right with a running product p = 1. At each index, before multiplying in the current element, record p into output[i]. Then p *= nums[i]. After this pass, output[i] is the product of nums[0..i-1].
• Right pass: walk right to left with a fresh running product p = 1. At each index, multiply output[i] *= p. Then p *= nums[i]. After this pass, output[i] is the product of nums[0..i-1] * nums[i+1..n-1].

No division, no extra arrays beyond the output, no auxiliary memory.

Step-by-step approach

1. Allocate output of length n.
2. Left-to-right: p = 1. For i = 0..n-1: output[i] = p; then p *= nums[i].
3. Right-to-left: p = 1. For i = n-1..0: output[i] *= p; then p *= nums[i].
4. Return output.

def product_except_self(nums):
    n = len(nums)
    output = [1] * n
    p = 1
    for i in range(n):
        output[i] = p
        p *= nums[i]
    p = 1
    for i in range(n - 1, -1, -1):
        output[i] *= p
        p *= nums[i]
    return output

Worked example

nums = [1, 2, 3, 4]

After the left pass, output[i] holds the prefix product:

output = [1, 1, 2, 6]. After the right pass, multiply in the suffix product:

Final output = [24, 12, 8, 6]. Verify: at index 1, product of others is 1 * 3 * 4 = 12.

The zero case is illuminating. nums = [-1, 1, 0, -3, 3]. After the left pass, output = [1, -1, -1, 0, 0]. After the right pass, output = [0, 0, 9, 0, 0]. The slot containing the zero gets product of all others = -1 * 1 * -3 * 3 = 9; every other slot's product includes the zero and is 0. No division, no special-casing.

Complexity

• Time: O(n), two linear passes.
• Space: O(1) auxiliary (the output array does not count by problem convention).

Brute force was O(n^2) time, O(1) space. Division trick was O(n) time, O(1) space but forbidden and zero-unsafe. The two-pass solution achieves the same asymptotic time without the division failure mode.

Common pitfalls

• Maintaining two separate left and right arrays: correct, but wastes O(n) auxiliary memory. The "multiply in place" two-pass trick uses only the output.
• Forgetting the initial p = 1: starting p = 0 zeroes out everything.
• Updating p before writing output[i] in the left pass: that includes nums[i] in the prefix, giving you the full prefix-up-to-and-including, not strict prefix. Off-by-one bug.
• Sneaking in a total / nums[i] "optimisation": explicitly forbidden by the spec and breaks on zeros. Even if a colleague suggests it as "cleaner", refuse.
• Integer overflow in fixed-width languages: the problem promises the answer fits in a 32-bit int, but intermediate products of all but one element can still overflow if you are not careful. Python is fine; C++/Java need 64-bit accumulators or per-step modulo if specified.
• Re-allocating output inside the loop: a beginner mistake, but it happens. Allocate once.

Where this shows up in the enterprise

• JPMorgan / Goldman Sachs portfolio leave-one-out exposure: as in the story.
• Stripe per-merchant chargeback risk score: a global multiplier with one-merchant-removed views, computed nightly for the trust-and-safety team.
• Amazon recommender feature engineering: prefix/suffix aggregates over user-event sequences (counts, sums, products) feed the model. The same two-pass shape applies to sums, mins, maxes.
• Snowflake window functions: LAG/LEAD and exclusive cumulative aggregates are built on this idea. Snowflake's query planner often compiles a "running prefix and suffix" into the executor.
• Pixar / DreamWorks render-pipeline lighting: prefix-suffix-product attenuation across a chain of light filters; remove one filter and recompute the rest.
• TSMC / Samsung chip yield analysis: leave-one-out wafer yield to find anomalous lots. Same multiplicative leave-one-out structure.
• Google Maps route-segment ETA composition: when one segment is excluded (closure), compose the remaining segments' multiplicative delays in O(n) once across an entire trip rather than O(n^2) recomputation on each closure.
• Robinhood portfolio "what if" simulator: per-position pull-out projections at constant time per position.

Variants you'll see elsewhere

• prefix-sum: the additive sibling. Same two-pass idea.
• running-sum-of-1d-array and find-pivot-index (in this bank): partial-aggregate idioms.
• largest-product-of-three-numbers: sort and pick extremes; uses no prefix product but shares the "product across array" framing.
• maximum-product-subarray: requires tracking both max and min running products to handle sign flips.
• prefix-max / prefix-min over arrays: same template with the max / min operator.
• range-product-query with a Fenwick tree: when the array is mutable.
• Map-reduce on associative operations: the same idea distributed across nodes.

The prefix/suffix idiom generalises to any associative operator: sum, product, GCD, max, min, XOR, matrix multiplication.

How parikshan turns this into a learning loop

Read this article, then click into practice. The editor runs your code against public tests plus per-session dynamic private tests generated fresh each attempt, so memorising a gist does not pass. Hints are graduated: free first hint, small penalty for the second, larger for the third. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each with a small integrity cost so you spend AI deliberately. In practice mode AI chat is free, the right place to debate the two-array vs in-place variants. After the verdict, one click in the dispute flow sends a contested result to a human reviewer. Attempt in practice mode first, internalise the two-pass shape, then exam mode without AI. When you can write both passes and explain the zero behaviour in under five minutes, the pattern is in your fingers.

In the AI-integrated workspace

An AI agent will reach for the division trick the moment it sees "product except self", because it is the shortest code. Your job is to:

1. Catch the division before it reaches review. The spec forbids it for principled reasons (zeros, integer precision). Generated code routinely violates it.
2. If the agent writes the two-pass solution, verify the order is correct: write output[i] = p before the multiply on the left pass; multiply before the right-pass p *= nums[i] update. Off-by-one in the running product is the most common bug.
3. Check the in-place optimisation. The two-array solution is correct but doubles memory. For million-element arrays in a hot path, that matters.
4. For fixed-width languages, verify the accumulator type is wide enough. The agent typically uses int in C++ and overflows on the n=20 stress test.
5. Confirm the algorithm handles n = 2 (boundary), all-zero, exactly-one-zero, and large negative values.

The candidate who reads the spec and says in five seconds, "prefix-suffix product, no division, two passes, O(1) extra" is the one who directs AI agents productively. The candidate who lets total / nums[i] ship is the one who explains the production zero-division outage to the post-mortem. parikshan trains the first kind.