Product except self: combine independent summaries

Split the excluded position out of the computation

The baseline multiplies every other element separately for each index: O(n²) multiplications and O(1) working space beyond output. Computing one total and dividing by the current element appears cheaper but violates the requirement and fails at zero. Ask instead which two disjoint pieces remain when position i is removed: everything strictly before it and everything strictly after it. Their products can be computed independently and combined.

The empty product is one because multiplying by one leaves the other side unchanged. It also explains the singleton result without a special mathematical exception. A first implementation can build separate prefix and suffix arrays, giving O(n) time and O(n) auxiliary storage. To meet the memory goal, write exclusive prefixes directly into the output, then walk backward with one suffix accumulator and multiply each output entry by that suffix.

In the forward pass, before index i, prefix is the product of nums[:i]; store it before multiplying by nums[i]. In the backward pass, before index i, suffix is the product of nums[i+1:]; combine it before incorporating nums[i]. These exclusive bounds prevent accidentally including the excluded element. The result takes O(n) arithmetic operations, O(1) auxiliary integer variables beyond the O(n) output. Python large integers occupy more than a machine word, so the strict bit-space/time cost grows with product magnitude.

Follow-up 1: work modulo a positive integer

Predict whether zero or a composite modulus breaks the two-pass method. Apply % modulus after every multiplication; associativity still holds, and no modular inverse is required.

Require a positive integer modulus and define modulus 1 as all zeros, including the singleton empty product. An approach based on division or inverses would fail for non-invertible entries even though the prefix/suffix method still works.

Follow-up 2: updates and repeated exclusion queries

The precomputed output becomes stale after a point update. For an associative operation, a segment tree stores interval products and updates only ancestors.

To exclude position 1, combine the query for [0, 1) with [2, 4); the root alone cannot answer it. Updates and one exclusion query cost O(log n), with O(n) stored state. Returning every exclusion result still costs at least O(n). A senior candidate distinguishes working space from output and derives both exclusive invariants. A lead candidate chooses between batch recomputation and an update-friendly structure using actual query/update ratios and numeric bounds.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/07-product-except-self
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

def product_except_self(nums):
    _integers(nums)
    result = [1] * len(nums)
    prefix = 1
    for i, value in enumerate(nums):
        result[i] = prefix
        prefix *= value
    suffix = 1
    for i in range(len(nums) - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

import itertools
import math
import unittest
from solution import product_except_self

class ProductTests(unittest.TestCase):
    def test_boundaries(self):
        self.assertEqual(product_except_self([]), [])
        self.assertEqual(product_except_self([7]), [1])
        self.assertEqual(product_except_self([0, 3, 4]), [12, 0, 0])
        self.assertEqual(product_except_self([0, 0, 4]), [0, 0, 0])
        nums = [2, 3, 4]
        self.assertEqual(product_except_self(nums), [12, 8, 6])
        self.assertEqual(nums, [2, 3, 4])
        with self.assertRaises(ValueError):
            product_except_self([False])

    def test_independent_exclusion_oracle(self):
        for n in range(6):
            for nums in itertools.product(range(-2, 3), repeat=n):
                expected = [math.prod(nums[:i] + nums[i+1:]) for i in range(n)]
                self.assertEqual(product_except_self(nums), expected)

if __name__ == "__main__":
    unittest.main()