Product of Array Except Self
Return an array `output` where `output[i]` is the product of all elements in `nums` except `nums[i]`. You must solve it in O(n) time without using the division operator. **Core Insight:** For each position `i`, the answer is (product of all elements to the left of i) × (product of all elements to the right of i). We can compute these two prefix/suffix products in two separate passes and multiply them together. **Algorithm:** First pass (left to right): build a `left` array where `left[i]` = product of all elements before index i. Second pass (right to left): maintain a running `right` product and multiply it into the output array. This avoids storing a separate right array. **Why no division:** Division would fail when a zero is present. The prefix/suffix approach handles zeros naturally. **Complexity:** Time O(n) — two passes. Space O(1) extra (the output array doesn't count as extra space per the problem statement).
Constraints
- •
2 ≤ nums.length ≤ 10⁵
def productExceptSelf(nums: list[int]) -> list[int]:
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result