Maximum Product Subarray - 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 = 'blue';

function visMainFunction(inputNums) {
    initClassProperties();
    
    startBatch();
    const nums = new VisArray(...inputNums);
    let result = nums[0];
    let maxProduct = result;
    let minProduct = result;
    let index = 1;

    makeVisVariable(index).registerAsIndexPointer(nums, CURRENT);
    makeVisVariable(maxProduct).options({label: 'maxProduct'}).createVis(true);
    makeVisVariable(minProduct).options({label: 'minProduct'}).createVis(true);
    makeVisVariable(result).options({label: 'result'}).createVis(true);
    endBatch();

    explanationAndColorPaletteNotifications();

    notification(`
        ▶️ <b>Initialization complete</b><br/>
        <ul style="margin:6px 0 0 16px;">
            <li><code>maxProduct = nums[0] = ${nums[0]}</code></li>
            <li><code>minProduct = nums[0] = ${nums[0]}</code></li>
            <li><code>result = nums[0] = ${nums[0]}</code> (global best so far)</li>
        </ul>
        We maintain both <code>maxProduct</code> and <code>minProduct</code> because multiplying by a negative reverses order between extensions:
        when <code>nums[i] &lt; 0</code>, <code>minProduct × nums[i]</code> ≥ <code>maxProduct × nums[i]</code>.<br/>
        🔄 Starting the loop from index ${makeColoredSpan(index, CURRENT_COLOR)}:  
        at each step we update <code>maxProduct</code> and <code>minProduct</code> by considering the new values obtained by either including the current number in the existing sequences yielding the <code>maxProduct</code> and <code>minProduct</code>, or starting a new sequence at the current index.<br/>
        We also update <code>result</code> as the maximum of its current value and the new <code>maxProduct</code>.
    `);

    while (index < nums.length) {
        startPartialBatch();

        const num = nums[index];
        const product1 = maxProduct * num;
        const product2 = minProduct * num;

        notification(`
            🔎 <b>Evaluate candidates at index</b> ${makeColoredSpan(index, CURRENT_COLOR)}<br/>
            Current value: <code>num</code> = <b>${makeColoredSpan(num, CURRENT_COLOR)}</b><br/><br/>
            Compute products with previous extremes:
            <ul style="margin:6px 0 0 16px;">
            <li><code>product1 = maxProduct × num</code> = <b>${maxProduct}</b> × <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> → <b>${product1}</b></li>
            <li><code>product2 = minProduct × num</code> = <b>${minProduct}</b> × <b>${makeColoredSpan(num, CURRENT_COLOR)}</b> → <b>${product2}</b></li>
            </ul>
            Update for this index:<br/>
            • <b>maxProduct</b> = <code>max(product1, product2, num)</code> = <b>${Math.max(product1, product2, num)}</b><br/>
            • <b>minProduct</b> = <code>min(product1, product2, num)</code> = <b>${Math.min(product1, product2, num)}</b><br/><br/>
            Finally, update global best:<br/>
            • <b>result</b> = <code>max(result, maxProduct)</code> = <b>${Math.max(result, Math.max(product1, product2, num))}</b>.
        `);
        
        maxProduct = Math.max(product1, product2, num);
        minProduct = Math.min(product1, product2, num);

        result = Math.max(maxProduct, result);

        index += 1;

        endBatch();
    }   

    notification(`✅ <b>Result:</b> The maximum product of any subarray is <b>${result}</b>.`);

    return result;
}

function explanationAndColorPaletteNotifications() {
    explanationNotification();

    notification(`
        🎨 <b>Color Palette Guide</b><br/><br/>
        • ${makeColoredSpan("Blue background", CURRENT_COLOR)} → <b>Current index pointer and value</b><br/>
    `);
}

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

Approach

Goal

Given an integer array nums, find the contiguous subarray with the largest product and return that product.

Key Idea (Intuition)

For a subarray that ends at index i, any candidate product must arise from either extending a previously tracked sequence or starting fresh at nums[i]. We therefore maintain two running values for subarrays ending at the current index:

maxProduct — maximum product ending at the current index
minProduct — minimum product ending at the current index

When nums[i] < 0, multiplying by a negative reverses order: among the two extension options we must compare, minProduct × nums[i] is greater than or equal to maxProduct × nums[i]. This reversal between the extension candidates is precisely why we maintain both the running maxProduct and minProduct at every step.

Initialization

maxProduct = nums[0]
minProduct = nums[0]
result = nums[0] (global best so far)
Start traversal at i = 1.

Traversal

For each index i from 1 to n - 1:

Form candidates for subarrays ending at i: c1 = maxProduct × nums[i], c2 = minProduct × nums[i], c3 = nums[i].
Update per-index extremes: maxProduct = max(c1, c2, c3); minProduct = min(c1, c2, c3).
Update global best: result = max(result, maxProduct).

Return

Return result as the maximum product of any contiguous subarray.

Time Complexity

The algorithm makes a single pass through the array of length n. At each index, it performs a constant amount of work: computing two products and updating maxProduct, minProduct, and result. Therefore, the time complexity is O(n).

Space Complexity

The algorithm uses only a constant amount of extra space for variables such as maxProduct, minProduct, result, and index. No additional data structures that grow with input size are required. Therefore, the space complexity is O(1).

Input-1

Maximum Product Subarray - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Goal

Key Idea (Intuition)

Initialization

Traversal

Return

Time Complexity

Space Complexity