Product of Array Except Self

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

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
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution

Approach: Prefix and Suffix Products

The key insight is that the product of all elements except nums[i] equals the product of all elements to its left multiplied by the product of all elements to its right.

We can compute this in two passes:

First pass: Calculate prefix products (product of all elements to the left)
Second pass: Calculate suffix products (product of all elements to the right) and multiply with prefix

Implementation

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

        # First pass: calculate prefix products
        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]

        # Second pass: calculate suffix products and multiply
        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]

        return result

Alternative (Using Separate Arrays):

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

        # Calculate prefix products
        for i in range(1, n):
            prefix[i] = prefix[i - 1] * nums[i - 1]

        # Calculate suffix products
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]

        # Combine prefix and suffix
        for i in range(n):
            result[i] = prefix[i] * suffix[i]

        return result

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. We make two passes through the array.
Space Complexity: O(1) for the optimal solution (not counting the output array). The alternative approach uses O(n) extra space for prefix and suffix arrays.

Key Insights

Left × Right Pattern: The product except self at index i equals (product of all left elements) × (product of all right elements). This breaks the problem into two simpler subproblems.
Two-Pass Solution: We can build the result in two passes - one for prefix products, one for suffix products - avoiding the need for division.
Space Optimization: By storing prefix products directly in the result array and calculating suffix products on the fly, we achieve O(1) extra space.
No Division Needed: While we could solve this by calculating the total product and dividing by each element, this approach fails when there are zeros and is explicitly forbidden by the problem.
Running Product: We maintain a running product variable that accumulates the product as we iterate, which is more space-efficient than storing all prefix/suffix products in separate arrays.