LeetCode 238 Product of Array Except Self: Prefix and Suffix Products Explained

Product of Array Except Self looks like a one-liner (multiply everything, divide by each element) until you read the rule that bans division. That rule is the point of the problem. It forces you to think of each answer as two independent pieces, what's on the left and what's on the right, and that decomposition is one of the most reusable ideas in array problems.

This guide covers the division approach and why it's banned, the prefix and suffix solution with a dry run, the O(1) extra space version interviewers ask for, zero handling, code in Python, C++ and Java, and how the same pattern solves other "everything except me" problems. It builds on ideas from prefix sum interview problems.

The Problem and Its Rules

Given an integer array nums, return an array answer such that answer[i] equals the product of all elements of nums except nums[i]. You must write an O(n) algorithm and must not use the division operation.

Constraints: 2 ≤ nums.length ≤ 10⁵, −30 ≤ nums[i] ≤ 30, and every prefix or suffix product is guaranteed to fit in a 32-bit integer. The follow-up asks for O(1) extra space, where the output array doesn't count.

Brute force

For each i, multiply every other element: O(n²). With n = 10⁵ that's 10¹⁰ multiplications, far too slow. The waste is obvious once you write it out: answer[3] and answer[4] share almost all of their factors, yet each is recomputed from scratch.

The Division Approach (and Why Zeros Break It)

The natural shortcut: compute the total product P once, then answer[i] = P / nums[i]. O(n) time, O(1) space. Two problems:

1. The problem forbids it. In an interview, though, mentioning it is fine and shows you see the simple version.
2. Zeros. If any element is 0, P is 0 and you can't divide by the zero element to recover the others' product.

You can patch it by counting zeros and multiplying only the non-zero elements:

def product_except_self_division(nums):
    zeros = nums.count(0)
    prod_nonzero = 1
    for x in nums:
        if x != 0:
            prod_nonzero *= x
    if zeros >= 2:
        return [0] * len(nums)
    if zeros == 1:
        return [prod_nonzero if x == 0 else 0 for x in nums]
    return [prod_nonzero // x for x in nums]   # exact: x divides the product

This works, and it's worth showing that you know the three zero cases. But it's a pile of special cases, it violates the rules, and it doesn't generalise: you can't "divide out" an element for operations like max or gcd, and under a modulus, an element may have no inverse. The prefix/suffix approach avoids all of that.

Prefix and Suffix Products

The product of everything except nums[i] is the product of the elements before i times the product of the elements after i:

Define two arrays (both exclusive, meaning they don't include index i itself):

• left[i] = product of nums[0..i−1], with left[0] = 1 (empty product).
• right[i] = product of nums[i+1..n−1], with right[n−1] = 1.

Each can be built in one pass, because left[i] = left[i−1] × nums[i−1] and right[i] = right[i+1] × nums[i+1]. Then answer[i] = left[i] × right[i].

def product_except_self_two_arrays(nums):
    n = len(nums)
    left = [1] * n
    right = [1] * n
    for i in range(1, n):
        left[i] = left[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        right[i] = right[i + 1] * nums[i + 1]
    return [left[i] * right[i] for i in range(n)]

Dry run on [1, 2, 3, 4]

Each left entry reuses the previous one with a single multiplication, which is where the O(n) comes from. The empty-product convention (1) handles the edges without special cases.

The O(1) Extra Space Version

The follow-up asks you to drop the extra arrays. Two observations make that possible:

1. The output array is free. Store the left products directly in answer.
2. The right products are consumed in order. Walking from the right end, you only ever need the product of everything you've passed so far. Keep it in one variable, suffix, multiply it into answer[i], then fold nums[i] into it.

Dry run on [1, 2, 3, 4]

Pass 1 (left to right): answer becomes the exclusive prefix products [1, 1, 2, 6].

The order inside the loop matters: multiply answer[i] by the suffix first, then include nums[i] in the suffix. Swapping those two lines includes the element itself and gives wrong answers. It's the single most common bug in this solution.

Code in Python, C++ and Java

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        prefix = 1
        for i in range(n):              # answer[i] = product of nums[0..i-1]
            answer[i] = prefix
            prefix *= nums[i]
        suffix = 1
        for i in range(n - 1, -1, -1):  # multiply in product of nums[i+1..n-1]
            answer[i] *= suffix
            suffix *= nums[i]
        return answer

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        int prefix = 1;
        for (int i = 0; i < n; ++i) {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        int suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }
};

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

A note on overflow

LeetCode guarantees prefix and suffix products fit in 32 bits. But look closely at the code: after the last iteration, prefix (and suffix) hold the product of the entire array, which isn't covered by that guarantee. In C++, signed overflow is undefined behaviour even if the value is never used. If you want to be strictly safe, skip the final multiplication or use a 64-bit type for the running variables:

vector<int> productExceptSelfSafe(const vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);
    long long prefix = 1, suffix = 1;
    for (int i = 0; i < n; ++i) {
        answer[i] = static_cast<int>(prefix);
        prefix *= nums[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        answer[i] = static_cast<int>(answer[i] * suffix);
        suffix *= nums[i];
    }
    return answer;
}

Even 64 bits only delays the problem on adversarial data, since the full product of 10⁵ values up to 30 is astronomically large. Under LeetCode's guarantee this version is fine; raising the point earns credit with interviewers who care about undefined behaviour, and Java's wrap-around makes the original code safe there in practice.

Complexity

Zero Handling Without Special Cases: Dry Run

The prefix/suffix method handles zeros on its own. Take nums = [−1, 1, 0, −3, 3].

Every index except 2 has the zero on one side, so its product is 0. Index 2 excludes the zero itself and gets (−1 × 1) × (−3 × 3) = 9. With two zeros, every index has at least one zero on some side, so the whole answer is 0. The algorithm never asks "is there a zero?", which is why it's preferred over the division version.

Edge cases checklist

• Length 2: [a, b] → [b, a]. The empty products at the ends do the work.
• Negative numbers: signs multiply normally; nothing special.
• All ones: all answers are 1.
• One zero / two zeros: covered above.
• Zero at the very start or end: e.g. [0, 4, 5] → [20, 0, 0].

Beyond Products: The "Except Self" Pattern

Nothing in the prefix/suffix argument depends on multiplication specifically. It works for any associative operation with an identity element: sum (identity 0), product (1), max (−∞), min (+∞), gcd (0), XOR (0), bitwise AND (all ones), bitwise OR (0). Division only works for operations with an inverse; prefix/suffix works for all of them.

from math import gcd

def except_self(nums, op, identity):
    n = len(nums)
    out = [identity] * n
    acc = identity
    for i in range(n):
        out[i] = acc
        acc = op(acc, nums[i])
    acc = identity
    for i in range(n - 1, -1, -1):
        out[i] = op(out[i], acc)
        acc = op(acc, nums[i])
    return out

nums = [12, 18, 6, 9]
print(except_self(nums, lambda a, b: a * b, 1))     # [972, 648, 1944, 1296]
print(except_self(nums, max, float('-inf')))        # [18, 12, 18, 18]
print(except_self(nums, gcd, 0))                    # [3, 3, 3, 6]

The gcd line answers a classic question directly: "remove exactly one element to maximise the gcd of the rest" is just max(except_self(nums, gcd, 0)). Max-except-self has no division-style shortcut at all, because you can't "un-max" an element. That's the strongest argument for knowing this pattern rather than the division trick.

Problems that use the same left/right decomposition

Trapping Rain Water is the closest cousin: water above bar i depends on the tallest bar on the left and the tallest on the right, built with exactly the same two passes (and squeezable to O(1) with two pointers). For a product problem with a different structure, contiguous subarrays rather than "all but one", see Maximum Product Subarray, which tracks running max and min instead.

Product of the Last K Numbers (1352): prefix products with zeros

Here division of prefix products is allowed, and zeros are handled by resetting the prefix list whenever a 0 arrives (any window containing it has product 0).

class ProductOfNumbers:
    def __init__(self):
        self.prefix = [1]                 # prefix[i] = product of the last i numbers since the last zero

    def add(self, num: int) -> None:
        if num == 0:
            self.prefix = [1]             # every window containing this zero is 0
        else:
            self.prefix.append(self.prefix[-1] * num)

    def getProduct(self, k: int) -> int:
        if k >= len(self.prefix):         # the window reaches back past a zero
            return 0
        return self.prefix[-1] // self.prefix[-1 - k]

It's a nice contrast: when division is permitted and zeros are managed explicitly, prefix ratios answer range queries in O(1). That's the multiplicative version of the range-sum trick in prefix sums.

How This Problem Shows Up in Interviews

Product of Array Except Self is commonly reported at Amazon, Microsoft, Meta, Apple and Indian product companies, typically as a 20-minute array question in a phone screen or first round. Because the core idea is well known, interviewers usually grade the details:

• Do you mention division and its zero problem before abandoning it?
• Can you state the decomposition ("left product times right product") before coding?
• Do you reach O(1) extra space, and correctly say the output array doesn't count?
• Do you dry run a zero case without being asked?
• Do you mention overflow?

A good 15-minute flow

1. Brute force O(n²), one sentence.
2. Division O(n) and why it's banned (zeros, rule).
3. Left × right decomposition with two arrays, quick dry run on [1, 2, 3, 4].
4. Optimise to O(1) extra with the running suffix; write the final code.
5. Dry run [−1, 1, 0, −3, 3]; state complexity; mention overflow.

Follow-ups to expect

• "Return the answer modulo 10⁹ + 7." Prefix/suffix works unchanged with % MOD after each multiplication. Division would need modular inverses, which don't exist for multiples of the modulus.
• "Do it in a single loop." Fill from both ends at once: index i gets the prefix, index n − 1 − i gets the suffix, in the same iteration. Still two "passes" of work, just interleaved.
• "What if the array updates?" A segment tree over products gives O(log n) updates and "product of everything except i" as the product of two range queries.
• "Max of everything except self?" Same pattern with max; or track the top two values in one pass.

Common Mistakes

• Including nums[i] in its own product: updating the running variable before writing answer[i].
• Initialising the running product to 0 instead of 1 (the multiplicative identity).
• Using division anyway and crashing on zero.
• Claiming O(n) space is O(1) when you kept separate left and right arrays.
• Claiming the output array is extra space when asked for the follow-up (it isn't, by the problem's definition).
• Forgetting overflow in the final running product in C++.

Once this pattern is second nature, you'll spot it in a surprising number of problems: anything that asks about "everything except i" or "the best on the left and the best on the right". It sits alongside two pointers and hashing in the core toolkit covered by array interview patterns, and next to Kadane's algorithm as one of the single-pass techniques worth knowing cold.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.