Product of Array Except Self in Python Without Division

Compute the product of all array elements except the current one in O(n) time using prefix and suffix products, without using division.

Medium Python 3.8+ Aug 9, 2026 Algorithms & data structures 13 views 0 copies

arrays prefix-product suffix-product

Python code

30 lines

Python 3.8+

from math import prod


def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]

    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]

    return result


if __name__ == "__main__":
    test_cases = [
        [1, 2, 3, 4],
        [-1, 1, 0, -3, 3],
        [2, 3, 5],
        [7],
    ]
    for case in test_cases:
        output = product_except_self(case)
        expected = [prod(case[:i] + case[i + 1:]) for i in range(len(case))]
        print(f"Input: {case} -> Output: {output} | Matches expected: {output == expected}")

Output

stdout

Input: [1, 2, 3, 4] -> Output: [24, 12, 8, 6] | Matches expected: True
Input: [-1, 1, 0, -3, 3] -> Output: [0, 0, 9, 0, 0] | Matches expected: True
Input: [2, 3, 5] -> Output: [15, 10, 6] | Matches expected: True
Input: [7] -> Output: [1] | Matches expected: True

How it works

The algorithm builds the result array in two passes. First pass computes the cumulative product of elements to the left of each index. Second pass multiplies by the cumulative product of elements to the right, iterating from the end. This achieves O(n) time and O(1) extra space (excluding output array). The logic utilizes the associative property of multiplication, avoiding division entirely.

Common mistakes

Using division to solve the problem initially, which fails with zero elements.
Forgetting to update the running product after assigning the current element.
Off-by-one errors when iterating backwards with the right product.

Variations

Use prefix and suffix arrays to store products for clarity, trading space for readability.
Solve with reduce from functools for a functional style, though it lacks the space efficiency.

Real-world use cases

Normalize a list of values by their overall product in statistics without dividing by zero.
Compute feature interaction terms in machine learning where each feature is scaled by product of others.
Generate payloads for recommendation systems where each item's influence is expressed as product of all others.

Product of Array Except Self in Python Without Division

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes