Product of Array Except Self

Given an array nums, return an array where each element is the product of every other element — without using division, and in O(1) extra space (the output array doesn't count).

Example

Input: 1 2 3 4 Output: 24 12 8 6

Approach

This is prefix sum's multiplicative cousin. Do two passes: a left-to-right pass fills each position with the product of everything before it (a running "prefix product"), then a right-to-left pass multiplies in the product of everything after it (a running "suffix product"). No division needed, and both passes reuse the output array itself as storage.

Walkthrough

1n = len(nums)
2result = [1] * n
3prefix = 1
4for i in range(n):
5    result[i] = prefix
6    prefix *= nums[i]
7suffix = 1
8for i in range(n - 1, -1, -1):
9    result[i] *= suffix
10    suffix *= nums[i]

Input format

Line 1: the array, space-separated

Print the result array, space-separated.