Problem Statement

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.

Additional information

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30

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]

Brute Force (Time Limit Exceeded)

Intuition
The most intuitive (naive) approach is to calculate the product for each element individually. For every index i, we can iterate through the entire array again and multiply all numbers where the index j is not equal to i. This does not strictly follow the "without division" rule if you consider the total product divided by nums[i], but typically "without division" implies finding a multiplicative way. This nested loop approach uses pure multiplication.

Algorithm

1. Initialize a result array res of the same length as nums.
2. Loop through each index i from 0 to n-1.
3. Inside, start a variable product = 1.
4. Loop through each index j from 0 to n-1.
5. If i != j, multiply product by nums[j].
6. Store product in res[i].
7. Return res.

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    res = [0] * n
    
    for i in range(n):
        product = 1
        for j in range(n):
            if i != j:
                product *= nums[j]
        res[i] = product
        
    return res

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: We have nested loops. For each of the n elements, we iterate through the other n-1 elements.

• Space complexity: O(1)

• Reason: We only use the output array and a single variable for the product.

Prefix and Suffix Arrays

Intuition
Since we cannot use division, we cannot simply multiply all numbers and divide by nums[i]. Instead, we can utilize the fact that the product of "all numbers except nums[i]" is equivalent to the product of all numbers to the left of i multiplied by the product of all numbers to the right of i.

Algorithm

1. Create an array left where left[i] contains the product of all numbers before index i.
2. Create an array right where right[i] contains the product of all numbers after index i.
3. The final answer for index i is left[i] * right[i].

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    left_products = [1] * n
    right_products = [1] * n

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

    for i in range(n - 2, -1, -1):
        right_products[i] = right_products[i + 1] * nums[i + 1]
    
    result = []
    for i in range(n):
        result.append(left_products[i] * right_products[i])
        
    return result

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the array three times (left pass, right pass, and final multiplication).

• Space complexity: O(n)

• Reason: We use two extra arrays (left_products and right_products) of size n.

Optimal (O(1) Space)

Intuition
We can optimize the space complexity by using the output array to store the prefix products directly. For the suffix products, we don't need a separate array; we can calculate them on the fly as we iterate backwards through the array. This reduces the auxiliary space usage to O(1) (excluding the output array).

Algorithm

1. Initialize the result array res with 1s.
2. Pass 1 (Prefix): Iterate forward. Store the product of all elements to the left of i in res[i].
3. Pass 2 (Suffix): Initialize a variable postfix to 1. Iterate backward. Multiply res[i] by postfix (which holds the product of all elements to the right of i), then update postfix by multiplying it with nums[i].

def product_except_self(nums: list[int]) -> list[int]:
    res = [1] * len(nums)

    prefix = 1
    for i in range(len(nums)):
        res[i] = prefix
        prefix *= nums[i]

    postfix = 1
    for i in range(len(nums) - 1, -1, -1):
        res[i] *= postfix
        postfix *= nums[i]

    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the array twice.

• Space complexity: O(1)

• Reason: We only use the output array (which typically doesn't count towards space complexity) and a few variables.