Start learning free

LESSON 447 OF 536 · DYNAMIC PROGRAMMING

Maximum Product Subarray in JavaScript: One Pass, O(n) Time, O(1) Space

Practice O(n) Read the full explanation

Given an array of integers nums, find the subarray with the largest product and return that product.

A subarray is a run of one or more elements that stand next to each other in nums. Its product is all of its elements multiplied together.

Example 1:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: The subarray [2, 3] has the largest product, 2 × 3 = 6. -2 is the only negative number, so every subarray that includes it has a negative product.

Example 2:

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The answer can't be 2: [-2, -1] is not a subarray, because 0 stands between them. The subarray [0] gives 0, and every other subarray gives 0 or less.

Example 3:

Input: nums = [-2, 3, -4]
Output: 24
Explanation: The whole array: the two negative numbers cancel out, -2 × 3 × -4 = 24.

Constraints:

  • 1 <= nums.length <= 105
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the length of nums.

STEP 1 OF 9
    Ctrl + Enter to check

    JAVASCRIPT · DYNAMIC PROGRAMMING

    Maximum Product Subarray in JavaScript, explained

    Problem overview

    maxProduct(nums) receives an array of integers and returns the largest product of a subarray: a run of one or more elements that stand next to each other. The product of a subarray is all its elements multiplied together.

    For [2, 3, -2, 4] the answer is 6, from [2, 3]: the only negative number, -2, makes every subarray that contains it negative. For [-2, 0, -1] the answer is 0. Taking [-2, -1] would give 2, but those two aren't next to each other, because the 0 stands between them. For [-2, 3, -4] the answer is 24, from the whole array, since the two negatives cancel.

    Approach: track the largest and the smallest product ending here

    For a sum, the best subarray ending at a position either extends the best one ending before it or starts fresh. A product has the same two choices, but with a twist: a negative number turns the smallest (most negative) product into the largest. So one running value isn't enough. At each position the solution keeps both the largest and the smallest product of a subarray that ends there: maxHere and minHere.

    Moving to the next element x:

    • if x is negative, the roles swap first, because multiplying by x turns the old smallest into the new largest and the other way round;
    • the new largest is the better of x alone and maxHere * x;
    • the new smallest is the lower of x alone and minHere * x.

    Starting fresh with x alone is also how a product gets past a 0: after a 0, both running values are 0, and the next element beats the product with 0 on its own. A separate variable, result, remembers the best maxHere seen at any position, since the best subarray ends somewhere.

    On [2, 3, -2, 4] the values after each element, as maxHere, minHere, result, are: start 2, 2, 2; after 3: 6, 3, 6; after -2: -2, -12, 6; after 4: 4, -48, 6. The answer is 6. On [-2, 3, -4] they are: start -2, -2, -2; after 3: 3, -6, 3; after -4: 24, -12, 24. The answer is 24.

    Step by step

    1. maxHere is a let variable starting at nums[0]. At the first element the only subarray ending there is the element itself.
    2. minHere also starts at nums[0].
    3. result starts at nums[0] too. A subarray needs at least one element, so the first element alone is a valid start even when it is negative.
    4. Loop with let i = 1 while i < nums.length. Element 0 is already counted.
    5. Negative element: if nums[i] < 0, swap the two with [maxHere, minHere] = [minHere, maxHere].
    6. Update the largest: maxHere = Math.max(nums[i], maxHere * nums[i]).
    7. Update the smallest: minHere = Math.min(nums[i], minHere * nums[i]).
    8. Update the best: result = Math.max(result, maxHere).
    9. Return result.

    The solution in JavaScript

    class Solution {
    maxProduct(nums) {
        let maxHere = nums[0];
        let minHere = nums[0];
        let result = nums[0];
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] < 0) {
                [maxHere, minHere] = [minHere, maxHere];
            }
            maxHere = Math.max(nums[i], maxHere * nums[i]);
            minHere = Math.min(nums[i], minHere * nums[i]);
            result = Math.max(result, maxHere);
        }
        return result;
    }
}

    Details worth knowing:

    • Swapping with destructuring. [maxHere, minHere] = [minHere, maxHere] builds an array of the two current values and unpacks it back into the variables in the other order, with no temporary variable. Both variables are declared with let above, so assigning to them is allowed.
    • The two updates don't interfere. The new maxHere is computed from the swapped values, and minHere uses its own old value, not maxHere, so the two lines don't interfere.
    • A line that starts with [ continues the previous line when that line has no semicolon. The reference code ends the statement before it with one, so the swap line stands alone.
    • Numbers are doubles. The lesson guarantees every subarray product fits in 32 bits, far below the point where a JavaScript number loses precision, so the products are exact.

    Complexity

    Time: O(n). One pass, with a few comparisons and multiplications per element.

    Space: O(1). Three numbers, whatever the length of the array.

    Edge cases and common mistakes

    • One negative element. [-3] gives -3. That is why result starts at nums[0] and not at 0.
    • A zero. [0] gives 0, and [-2, 0] gives 0. A product through a 0 is 0, and the next element starts a new run.
    • Two negatives. [-1, -1] gives 1. The first -1 is the smallest product so far, and multiplying it by the second -1 makes it the largest.
    • A negative in the middle of a long run. [2, -5, -2, -4, 3] gives 24, from [-2, -4, 3]. Keeping only the largest product would lose the -5 that a later negative could have used.
    • Keeping only maxHere. [-2, 3, -4] would then give 3 instead of 24.
    • Starting result at 0. An array like [-3] would wrongly return 0.
    • Swapping after the multiplication. The swap must come before the two updates, or each product uses the wrong running value.

    Testing

    • [2, 3, -2, 4] gives 6.
    • [-2, 0, -1] gives 0.
    • [-2, 3, -4] gives 24.
    • [-3] gives -3.
    • [0, -1] gives 0.
    • [-1, -1] gives 1.
    • [2, -5, -2, -4, 3] gives 24.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free