Product Except Self¶

Problem¶

Given an integer array, return an array where each element is the product of all other elements. Do not use division.

Approach¶

Two-pass prefix/suffix products. First pass builds prefix products left-to-right, second pass multiplies in suffix products right-to-left. Uses the output array itself to store prefix, then folds in suffix with a running variable.

When to Use¶

Prefix/suffix accumulation without division — product, sum, or any associative operation where you need "everything except index i". Also: running totals, range queries without a segment tree.

Complexity¶


Time	`O(n)`
Space	`O(1) (output array not counted)`

Implementation¶

SolutionTestsChallenge

product_except_self ¶

Product of Array Except Self — product of all elements except self.

Problem

Given an integer array, return an array where each element is the product of all other elements. Do not use division.

Approach

Two-pass prefix/suffix products. First pass builds prefix products left-to-right, second pass multiplies in suffix products right-to-left. Uses the output array itself to store prefix, then folds in suffix with a running variable.

When to use

Prefix/suffix accumulation without division — product, sum, or any associative operation where you need "everything except index i". Also: running totals, range queries without a segment tree.

Complexity

Time: O(n) Space: O(1) (output array not counted)

product_except_self ¶

product_except_self(nums: Sequence[int]) -> list[int]

Return array of products of all elements except nums[i].

product_except_self([1, 2, 3, 4]) [24, 12, 8, 6]

Source code in src/algo/arrays/product_except_self.py

def product_except_self(nums: Sequence[int]) -> list[int]:
    """Return array of products of all elements except nums[i].

    >>> product_except_self([1, 2, 3, 4])
    [24, 12, 8, 6]
    """
    n = len(nums)
    result = [1] * n

    # Prefix pass: result[i] = product of nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Suffix pass: multiply in product of nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

tests/arrays/test_product_except_self.py

"""Tests for the product-except-self problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.arrays.product_except_self import product_except_self


class TestProductExceptSelf:
    def test_basic(self) -> None:
        assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]

    def test_contains_zero(self) -> None:
        assert product_except_self([0, 1, 2, 3]) == [6, 0, 0, 0]

    def test_two_zeros(self) -> None:
        assert product_except_self([0, 0, 2]) == [0, 0, 0]

    def test_negative_numbers(self) -> None:
        assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]

    def test_two_elements(self) -> None:
        assert product_except_self([5, 3]) == [3, 5]

    def test_single_element(self) -> None:
        assert product_except_self([42]) == [1]

    @given(
        data=st.lists(
            st.integers(min_value=-10, max_value=10),
            min_size=1,
            max_size=20,
        ),
    )
    def test_matches_brute_force(self, data: list[int]) -> None:
        import math

        result = product_except_self(data)
        for i, val in enumerate(result):
            expected = math.prod(data[:i]) * math.prod(data[i + 1 :])
            assert val == expected

Implement it yourself

Run: just challenge arrays product_except_self

Then implement the functions to make all tests pass. Use just study arrays for watch mode.

Reveal Solution

product_except_self ¶

Product of Array Except Self — product of all elements except self.

Problem

Given an integer array, return an array where each element is the product of all other elements. Do not use division.

Approach

Two-pass prefix/suffix products. First pass builds prefix products left-to-right, second pass multiplies in suffix products right-to-left. Uses the output array itself to store prefix, then folds in suffix with a running variable.

When to use

Prefix/suffix accumulation without division — product, sum, or any associative operation where you need "everything except index i". Also: running totals, range queries without a segment tree.

Complexity

Time: O(n) Space: O(1) (output array not counted)

product_except_self ¶

product_except_self(nums: Sequence[int]) -> list[int]

Return array of products of all elements except nums[i].

product_except_self([1, 2, 3, 4]) [24, 12, 8, 6]

Source code in src/algo/arrays/product_except_self.py

def product_except_self(nums: Sequence[int]) -> list[int]:
    """Return array of products of all elements except nums[i].

    >>> product_except_self([1, 2, 3, 4])
    [24, 12, 8, 6]
    """
    n = len(nums)
    result = [1] * n

    # Prefix pass: result[i] = product of nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Suffix pass: multiply in product of nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result