Product of Array Except Self

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.

Example:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Approach: Prefix and Postfix Products

A brute force approach would be to calculate the total product of the array and then divide by nums[i] for each element, but the problem strictly forbids using division (and it breaks if there is a 0 in the array).

Instead, the product of the array except nums[i] is equivalent to:
(The product of all elements to the left of i) $\times$ (The product of all elements to the right of i)

We can compute this in two passes while using $O(1)$ extra space (excluding the output array):

1. Initialize a result array of the same length as nums, filled with 1.
2. Initialize a variable prefix = 1.
3. First Pass (Left to Right): Iterate through nums. For each element at index i, set result[i] = prefix, and then update prefix = prefix * nums[i]. This stores the product of all elements strictly to the left of i.
4. Initialize a variable postfix = 1.
5. Second Pass (Right to Left): Iterate backwards through nums. For each element at index i, multiply the existing result[i] by postfix (so result[i] = result[i] * postfix), and then update postfix = postfix * nums[i]. This multiplies the left product by the product of all elements strictly to the right of i.
6. Return the result array.

Solution

function productExceptSelf(nums) {
    const result = new Array(nums.length).fill(1);
    
    // First pass: Calculate prefix products
    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = prefix;
        prefix *= nums[i];
    }
    
    // Second pass: Calculate postfix products and multiply
    let postfix = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= postfix;
        postfix *= nums[i];
    }
    
    return result;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the number of elements in the array. We make exactly two distinct passes over the array, making the time linear.
• Space Complexity: $O(1)$ auxiliary space. The problem description specifies that the output array does not count as extra space for the purpose of space complexity analysis. We only use two variables (prefix and postfix).