Product of Array Except Self

How it works

We can compute the product of all elements except the current one without using extra prefix and suffix arrays. Instead, we reuse the result array and build the answer in two simple passes:

• In the first pass, we fill res[i] with the product of all elements to the left of i (prefix product).
• In the second pass, we multiply each res[i] with the product of all elements to the right of i (postfix product).

By maintaining two running values — prefix and postfix — we avoid the need for separate pref and suff arrays. This gives us the same logic as the previous method, but with O(1) extra space.

Steps

1. Initialize the result array res with all values set to 1.
2. Create a variable prefix = 1.
3. First pass (left to right):
   • For each index i:
     • Set res[i] = prefix (product of all elements to the left).
     • Update prefix *= nums[i].
4. Create a variable postfix = 1.
5. Second pass (right to left):
   • For each index i:
     • Multiply res[i] by postfix (product of all elements to the right).
     • Update postfix *= nums[i].
6. Return the result array res.

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) space for the output array.

Things to watch for

Using Division Without Handling Zeros

The division approach (totalProduct / nums[i]) fails when the array contains zeros. Dividing by zero causes runtime errors, and having multiple zeros requires special handling. Always count zeros first: with two or more zeros, the entire result is zeros; with exactly one zero, only the zero's position gets the product of other elements.

Off-by-One Errors in Prefix/Suffix Array Construction

When building prefix products, pref[i] should contain the product of elements before index i, not including nums[i]. A common mistake is including nums[i] in the prefix, which double-counts the element. The same applies to suffix arrays: suff[i] should exclude nums[i].

Integer Overflow with Large Products

When the array contains many large numbers, the product can overflow 32-bit integers. In languages with fixed-size integers, consider using long or BigInteger. The problem constraints usually prevent overflow, but edge cases with many elements near the maximum value should be tested.

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * (len(nums))

        prefix = 1
        for i in range(len(nums)):
            res[i] = prefix
            prefix *= nums[i]
        postfix = 1
        for i in range(len(nums) - 1, -1, -1):
            res[i] *= postfix
            postfix *= nums[i]
        return res

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);

        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }

        int postfix = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= postfix;
            postfix *= nums[i];
        }
        return res;
    }
};