leetcode-238 Product of Array Except Self

[238] Product of Array Except Self

Key Concept: Prefix and Suffix Products - Build the result by calculating the product of all elements to the left, then multiply by the product of all elements to the right. This avoids division and handles zeros elegantly.

Algorithm:

First pass: Calculate prefix products (product of all elements before current)
Second pass: Multiply by suffix products (product of all elements after current)

# Given an integer array nums, return an array answer such that answer[i] is
# equal to the product of all elements of nums except nums[i].
#
# You must write an algorithm that runs in O(n) time and without using division.
#
# Example 1:
# Input: nums = [1,2,3,4]
# Output: [24,12,8,6]
#
# Example 2:
# Input: nums = [-1,1,0,-3,3]
# Output: [0,0,9,0,0]
#
# Constraints:
# 2 <= nums.length <= 10^5
# -30 <= nums[i] <= 30

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n

        # Calculate prefix products
        # result[i] will contain product of all elements before i
        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]

        # Calculate suffix products and multiply with prefix
        # result[i] will contain product of all elements except nums[i]
        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]

        return result

# Time Complexity: O(n) - two passes through the array
# Space Complexity: O(1) - output array doesn't count as extra space