Topic: Learning notes

LeetCode 238: Product of array except self with prefix and suffix products

My division-based solution and prefix/suffix version, with zero handling, loop invariants, executable tests, and the difference between extra and output space.

My first idea was to calculate the total product, then divide by the current number. I handled zeros separately. In my second version, I stored the product on the right and multiplied it by the product on the left. That removed both division and special branches for zeros.

Both solutions below are mine. The cleaned-up version changes names and types without replacing the algorithm. The correctness explanation and tests are additions for this article.

The problem and its constraints

LeetCode 238: Product of Array Except Self asks for the product of every element except the one at each output position. For example, [1, 2, 3, 4] produces [24, 12, 8, 6]. The first result is 2 × 3 × 4.

The input contains 2 to 100000 integers, each between -30 and 30. The problem guarantees that every prefix product, suffix product, and answer fits in a signed 32-bit integer. The required runtime is O(n), without division. The follow-up asks for O(1) extra space, excluding the output array.

My first solution used division

I renamed this function so that both versions can appear in the same file.

function productExceptSelfWithDivision(nums: number[]): number[] {
    let hasZero = false;
    const total = nums.reduce((acc, b) => {
        if (b === 0 && !hasZero) {
            hasZero = true;
            return acc;
        } else {
            return acc * b;
        }
    }, 1);
    return nums.map(num => num === 0 ? total : hasZero ? 0 : total / num);
}

hasZero records whether a zero has appeared. The code skips only the first zero. A second zero still participates in the multiplication.

This version handles multiple zeros while its accumulator stays finite. With [-1, 0, 0, -3, 3], it skips the first zero, but the second one still makes the running product zero.

Skipping a zero produces an intermediate product outside the prompt’s prefix guarantee. Consider [0, ...new Array(220).fill(30), 0]. Every prefix and suffix product is zero, and every answer is zero, so this is a valid input.

After skipping the initial zero, the first version accumulates 30 to the power of 220. That exceeds the JavaScript Number range and becomes Infinity. Multiplying it by the final zero produces NaN. Besides violating the division restriction, this version therefore fails on a valid input. The table above assumes finite arithmetic. MDN Infinity describes overflow behavior, and the tests below reproduce the full case.

Its problem is division, which the prompt forbids. Runtime is O(n), extra space is O(1), and the returned array takes O(n) space. Matching sample outputs does not remove that restriction.

An added brute-force reference

This was not my first submission. It is a reference implementation for comparison: fix position i, then multiply the elements at all other positions.

function productExceptSelfBruteForce(nums: number[]): number[] {
    return nums.map((_, i) =>
        nums.reduce((product, value, j) => j === i ? product : product * value, 1)
    );
}

Recalculating n − 1 elements for each position costs O(n²). Neighboring output positions repeat much of the same work. This reference is used for small integer tests. An intermediate product formed by skipping an arbitrary element is not necessarily covered by the prompt’s prefix/suffix guarantee, so it is not a general exact-arithmetic oracle for large numbers.

My improved prefix and suffix solution

I first scan from the right and store the product to the right of each position. Then I scan from the left and multiply by the product to its left. The code below preserves that order, corrects sufix to suffix, renames arr to answer, and adds the array type.

function productExceptSelf(nums: number[]): number[] {
    const answer = new Array<number>(nums.length);
    let suffix = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        answer[i] = suffix;
        suffix *= nums[i];
    }

    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        answer[i] *= prefix;
        prefix *= nums[i];
    }
    return answer;
}

Each result has two parts:

answer[i] = product to the left × product to the right

Neither part includes nums[i]. For [1, 2, 3, 4]:

There are no elements to the right of the last position, so that product is 1. The first position has the same empty product on its left. Multiplying by 1 leaves the other side unchanged. Starting at zero would make every accumulated product zero.

Why the update order matters

At the start of the first loop’s iteration for i, suffix equals the product of all elements strictly to the right of i.

The loop stores that value in answer[i], then multiplies it by nums[i]. This prepares the right-side product for the next position to the left. At the rightmost position, the initial value 1 matches the empty product. Repeating these steps stores a product that excludes the current element at every position.

At the start of the second loop’s iteration for i, prefix equals the product strictly to the left of i. The entry answer[i] still contains the right-side product. Multiplying them includes every other position exactly once. Updating prefix afterward prepares it for the next iteration.

If prefix *= nums[i] came before the answer update, the result would include the element it must exclude. The first pass has the same ordering requirement.

Zeros require no branches. With one zero, only the zero’s own position can exclude it. With two zeros, excluding any single position still leaves a zero in the product.

What O(1) space counts

Each pass takes O(n) time, so two passes still take O(n). Producing n output values already requires linear work in this computation model.

The accumulators and indices use a fixed number of variables, giving O(1) extra space. The output contains n values and uses O(n) space. Including that output, total space is O(n). The division version has the same space classification. The improvement removes division and zero-handling branches, not the output array.

Separate left-product and right-product arrays are unnecessary. Combining both directions into one loop is also unnecessary. Two passes make the correspondence with the correctness argument easy to inspect.

Executable tests

Place both functions and the following code in one TypeScript file and run it in a TypeScript-capable environment. The tests check that the input stays unchanged. The last assertion reproduces the first version’s overflow failure.

import assert from "node:assert/strict";

function check(nums: number[], expected: number[]): void {
    const original = [...nums];
    const actual = productExceptSelf(nums);
    assert.equal(actual.length, expected.length);
    actual.forEach((value, i) => assert.ok(value === expected[i]));
    assert.deepStrictEqual(nums, original);
}

check([1, 2, 3, 4], [24, 12, 8, 6]);
check([-1, 1, 0, -3, 3], [0, 0, 9, 0, 0]);
check([-1, 0, 0, -3, 3], [0, 0, 0, 0, 0]);
check([2, 3], [3, 2]);
check([-1, -2, -3], [6, 3, 2]);
check([0, 0], [0, 0]);
check([0, ...new Array(220).fill(30), 0], new Array(222).fill(0));
assert.ok(productExceptSelfWithDivision([0, ...new Array(220).fill(30), 0]).some(Number.isNaN));

JavaScript multiplication can produce -0. The === operator treats it as equal to 0, while Node.js strict assertions distinguish them. These tests check the length first, then compare output values individually with numeric equality. They use deepStrictEqual to check the unchanged input. There is no need to modify the algorithm just to display positive zero. Node.js assertion documentation

Both versions also matched the brute-force reference on 19525 arrays of lengths 2 through 6, using values from -2 through 2 and normalizing signed zeros. This finite check supports the implementation but does not replace the proof or make the division version compliant with the prompt.

What I want to retain

An output that excludes the current element can combine accumulated results from both sides. Those products do not need to be recalculated at each position. Defining exactly what each accumulator contains at the start of an iteration makes the update order easier to check.

My second version already meets the linear-time and constant-extra-space requirements. The next practice is explaining both loop invariants without relying on the code and turning examples into tests that actually fail on incorrect results.

References

• LeetCode 238: Product of Array Except Self: problem, constraints, and output-space convention.
• Node.js assert: assertions and signed-zero comparison.
• MDN Infinity: arithmetic beyond the numeric range.