Product of Array Except Self

Concept

LeetCode #238.
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]. You must write an algorithm that runs in $O(N)$ time and without using the division operation.

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
(Index 0 is 2 * 3 * 4 = 24).

The Division Trap

If the problem allowed division, this would be a 30-second problem.
You just loop through the array once and multiply every single number together. 1 * 2 * 3 * 4 = 24.
Then you loop through the array again. For index i, you just take the global total and divide it by the current number!
24 / 1 = 24. 24 / 2 = 12.

But the problem explicitly forbids the division operator (/), completely destroying this approach.

The Prefix/Suffix DP Strategy ($O(N)$ Space)

If we are standing at index 2 (the number 3), the “Product of Array Except Self” is mathematically equal to:
(The product of everything to its LEFT) $\times$ (The product of everything to its RIGHT).

We can pre-calculate these values!

1. Build a prefix array. Iterate left-to-right. prefix[i] holds the rolling product of all numbers strictly to the LEFT of i.
2. Build a suffix array. Iterate right-to-left. suffix[i] holds the rolling product of all numbers strictly to the RIGHT of i.
3. Loop through the original array. The answer for index i is simply prefix[i] * suffix[i]!

The Optimal Approach ($O(1)$ Space)

The prompt asks if we can do it in $O(1)$ extra space. (The output answer array doesn’t count towards the limit).
We can eliminate the prefix and suffix arrays! We just use the answer array itself to hold the data, and use a sliding integer variable to do the math on the fly.

The Algorithm:

1. Initialize the answer array with 1s.
2. First Pass (Left to Right): We use a variable leftProduct (starts at 1). We walk through the array. At index i, we dump the leftProduct into answer[i]. Then, we multiply leftProduct by nums[i] and move forward! (This flawlessly fills the answer array with the Prefix data!).
3. Second Pass (Right to Left): We use a variable rightProduct (starts at 1). We walk backward. At index i, we multiply whatever is already sitting in answer[i] by the rightProduct. Then, we multiply rightProduct by nums[i] and move backward!

Implementation

// Time Complexity: O(N) (Two passes)
// Space Complexity: O(1) (The output array does not count as extra space)

function productExceptSelf(nums: number[]): number[] {
    const length = nums.length;
    const answer = new Array(length).fill(1);

    // --- PASS 1: The Prefix (Left to Right) ---
    // We start with 1 because there is nothing to the left of the 0th element
    let leftProduct = 1; 
    
    for (let i = 0; i < length; i++) {
        // Dump the rolling product into the answer array!
        answer[i] = leftProduct;
        
        // Multiply the rolling product by the CURRENT number, 
        // to prepare it for the next iteration!
        leftProduct *= nums[i];
    }

    // --- PASS 2: The Suffix (Right to Left) ---
    // We start with 1 because there is nothing to the right of the last element
    let rightProduct = 1;
    
    for (let i = length - 1; i >= 0; i--) {
        // Multiply the prefix (which is already sitting in the array) 
        // by the rolling suffix!
        answer[i] *= rightProduct;
        
        // Multiply the rolling suffix by the CURRENT number,
        // to prepare it for the next iteration!
        rightProduct *= nums[i];
    }

    return answer;
}

Interview Questions

Q: What if the division operator was allowed, but the array contains the number 0? (e.g., [1, 2, 0, 4])
A: This is why the division approach is secretly a trap even if it wasn’t forbidden. If you multiply the entire array together, the global total instantly collapses to 0. When you do the second loop and attempt to divide 0 / 0 at index 2, the CPU will throw a catastrophic DivideByZero Exception (or return NaN in JS). To fix the division approach, you have to write complex if/else logic to specifically count the number of zeros in the array and handle them as isolated edge cases. The Prefix/Suffix approach is vastly superior because multiplication handles zeros flawlessly without any edge case logic!