Product of Array Except Self - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'orange';

function visMainFunction(inputNums) {
    initClassProperties();

    startBatch();
    const nums = new VisArray(...inputNums);
    const result = new VisArray(nums.length);
    let product = 1;
    let index = 0;
    
    makeVisVariable(product).options({label: 'product'}).createVis(true);
    makeVisVariable(index).registerAsIndexPointer(nums, CURRENT);
    endBatch();

    explanationAndColorPaletteNotifications();

    notification(`
        🚶 <b>Starting left-to-right traversal:</b><br/>
        In this pass, we compute the <b>product of all elements to the left</b> of each index and store it in the result array.<br/>
        Since there are no elements to the left of index <code>0</code>, it starts with <code>1</code>.
    `);
    

    while (index < nums.length) {
        startPartialBatch();
        notification(`
            Writing the current <b>product (${product})</b> to <code>result[${makeColoredSpan(index, CURRENT_COLOR)}]</code>.<br/>
            Here, <b>product</b> represents the <b>left product for this index</b>, which is why we store it in the result array in this pass.<br/>
        `);
        result[index] = product;
        notification(`
            Updating product by multiplying with the current number:<br/>
            <b>${product} × nums[${index}] (${makeColoredSpan(nums[index], CURRENT_COLOR)})</b>.<br/>
            This prepares <b>product</b> to be the left product for the <i>next</i> index.
        `);
        product *= nums[index];

        index += 1;
        endBatch();
    }
    
    startPartialBatch();
    // Reset product for the right-to-left traversal
    product = 1;
    index = nums.length - 1;
    notification(`
        ✅ <b>Left-to-right traversal complete!</b><br/>
        The result array now holds the product of all elements to the left of each index.<br/>
        🔄 Resetting <b>product</b> to <code>1</code> and starting <b>right-to-left traversal</b>:<br/>
        This time, we multiply the values in the result array with the <b>product of all elements to the right</b> of each index.
    `);
    endBatch();

    while (index >= 0) {
        startPartialBatch();
        notification(`
            Multiplying <code>result[${index}]</code> (currently holding the <b>left product</b> for index ${makeColoredSpan(index, CURRENT_COLOR)}: <b>${result[index]}</b>)
            by <b>product (${product})</b> to factor in the product of all elements to the right.<br/>
        `);
        result[index] *= product;
        notification(`
            Updating product by multiplying with the current number:<br/>
            <b>${product} × nums[${index}] (${makeColoredSpan(nums[index], CURRENT_COLOR)})</b>.<br/>
            This prepares <b>product</b> to be the right product for the <i>previous</i> index in the next iteration.
        `);
        product *= nums[index];

        index -= 1;
        endBatch();
    }

    notification(`
        🎉 Traversal complete!<br/>
        <b>The final result array</b> contains the product of all elements except self for each index.
    `);

    return result;
}

function explanationAndColorPaletteNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Palette Guide</b><br/><br/>
        • ${makeColoredSpan("Orange", CURRENT_COLOR)} → <b>Current index / number being processed</b><br/>
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        'backgroundColor': CURRENT_COLOR
    });
}

Approach

Goal

Given an array nums, build an array result where result[i] equals the product of all elements in nums except nums[i], without using division.

Key Idea (Intuition)

For each index i, the answer is the product of all elements to its left times the product of all elements to its right. We can compute this in two linear passes using a single running product variable: first fill result[i] with the left product for each index, then traverse from right to left and multiply in the right product.

Initialization

Create result with length n.
Set product = 1 — a running product variable.
It will represent the left product of the current index during the left-to-right traversal and the right product of the current index during the right-to-left traversal.

Traversal — Left to Right

For each index i from 0 to n-1:

Write the current product into result[i] — this is the left product for index i.
Update product by multiplying with nums[i] so it becomes the left product for the next index.

Traversal — Right to Left

Reset product = 1 and iterate i from n-1 down to 0: In this pass, product represents the right product for the current index.

result[i] currently holds the left product for index i. Multiply it by the current product to factor in the right product.
Update product by multiplying with nums[i] so it becomes the right product for the previous index in the next step.

Return

After both passes, result contains the product of all elements except self for each index. Return result.

Time Complexity

The algorithm makes two full passes over the array: one left-to-right and one right-to-left. Each step only involves constant-time operations (multiplication and assignment). Therefore, the time complexity is O(n), where n is the length of the input array.

Space Complexity

The algorithm uses only a constant amount of extra space for variables such as product and index, so the extra space complexity is O(1). However, we also allocate the result array to hold the output, which requires O(n) space. Thus overall, the algorithm uses O(1) extra space and O(n) space for the output.

Input-1

Product of Array Except Self - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Goal

Key Idea (Intuition)

Initialization

Traversal — Left to Right

Traversal — Right to Left

Return

Time Complexity

Space Complexity