Start learning free

LESSON 451 OF 540 · DYNAMIC PROGRAMMING

Maximum Product Subarray in Scala: 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 <= 10⁵
-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 11

Guided

Ctrl + Enter to check

SCALA · DYNAMIC PROGRAMMING

Maximum Product Subarray in Scala, explained

Problem overview

maxProduct receives an Array[Int], nums, and returns the largest product of a subarray: a run of one or more elements that stand next to each other. The product is all the elements of the run multiplied together. The values are between -10 and 10, and every subarray product fits in an Int.

For [2, 3, -2, 4] the answer is 6, from [2, 3]; the only negative number is -2, so any subarray that includes it has a negative product. For [-2, 0, -1] the answer is 0: [-2, -1] isn't a subarray, because the 0 stands between them. For [-2, 3, -4] the answer is 24, the whole array, where the two negatives cancel out.

Approach: track the largest and the smallest product ending here

The sum version of this problem keeps one running value. Products need two, because of the signs. A very negative product turns into a very positive one the moment it is multiplied by a negative number. So at each element, the code keeps both:

maxHere, the largest product of a subarray that ends at the current element;
minHere, the smallest (most negative) product of a subarray that ends there.

When the next element x arrives, the best subarray ending at it either starts fresh at x or extends one that ended at the previous element, so the candidates are x, maxHere * x and minHere * x. If x is negative, multiplying flips the order: the old smallest gives the new largest. Swapping maxHere and minHere first, when x is negative, lets the same two formulas work for both signs. Starting fresh is also how a product gets past a 0: after a 0, both values restart from the next element.

A separate result records the best maxHere seen anywhere, since the best subarray can end at any element. One pass with a few variables gives O(n) time and O(1) extra space.

Step by step

var maxHere = nums(0). At the first element, the only subarray ending there is the element itself. It is a var because it changes in the loop.
var minHere = nums(0), for the same reason.
var result = nums(0). A subarray must have at least one element, so the first element alone is a valid start even when it is negative.
Loop with i <- 1 until nums.length. Element 0 is already counted in all three variables.
Negative element. Inside the loop, if (nums(i) < 0): multiplying by a negative number flips the order, so the two values must trade places before they are used.
Save maxHere in val temp, so that the next assignment doesn't lose it.
Swap. Copy minHere into maxHere and temp into minHere.
New maximum. maxHere = math.max(nums(i), maxHere * nums(i)): start fresh at i, or extend.
New minimum. minHere = math.min(nums(i), minHere * nums(i)): the same two choices, keeping the smallest.
Update the answer: result = math.max(result, maxHere).
Return result after the loop, as the last expression.

The solution in Scala

class Solution {

    def maxProduct(nums: Array[Int]): Int = {
        var maxHere = nums(0)
        var minHere = nums(0)
        var result = nums(0)
        for (i <- 1 until nums.length) {
            if (nums(i) < 0) {
                val temp = maxHere
                maxHere = minHere
                minHere = temp
            }
            maxHere = math.max(nums(i), maxHere * nums(i))
            minHere = math.min(nums(i), minHere * nums(i))
            result = math.max(result, maxHere)
        }
        result
    }
}

Here is the state after each element for [2, 3, -2, 4]:

start maxHere=2 minHere=2 result=2
i=1 nums(i)=3 maxHere=6 minHere=3 result=6
i=2 nums(i)=-2 maxHere=-2 minHere=-12 result=6
i=3 nums(i)=4 maxHere=4 minHere=-48 result=6

At i = 2 the swap runs first, so maxHere is 3 and minHere is 6; then maxHere becomes the larger of -2 and 3 * -2, which is -2, and minHere the smaller of -2 and 6 * -2, which is -12. At i = 3 there is no swap, and the best subarray ending at 4 is 4 alone, so result stays 6.

And for [-2, 3, -4], where two negatives meet:

start maxHere=-2 minHere=-2 result=-2
i=1 nums(i)=3 maxHere=3 minHere=-6 result=3
i=2 nums(i)=-4 maxHere=24 minHere=-12 result=24

At i = 2 the swap makes maxHere equal -6, the old smallest, and -6 * -4 gives 24.

Scala details worth knowing:

val versus var. maxHere, minHere and result are var because they change. temp is a val, created fresh each time the if body runs.
until. 1 until nums.length excludes the end, so the loop visits indexes 1 to length - 1. For a one-element array it is empty and the loop doesn't run.
math.max and math.min take two numbers; here they work on Int values and return an Int.
The last expression is the result. result on its own line ends the method, so there is no return.
Overflow. Int is 32 bits and overflow wraps silently. The lesson guarantees that every subarray product fits, and the code only multiplies a running product by one more element, so every value it forms is a subarray product. Nine tens in a row give 1000000000, which still fits.

Complexity

Time: O(n). The loop makes one pass over the array and does a constant amount of work per element: at most one swap, two multiplications and three comparisons.

Space: O(1). The code stores only the three running values and temp, however long the array is.

Edge cases and common mistakes

A single element. [-3] gives -3 and [0] gives 0. Starting result at 0 instead of nums(0) would wrongly return 0 for [-3].
Zeros. [-2, 0, -1] gives 0. At the 0, both maxHere and minHere become 0, and at the next element they restart from that element alone, so the -2 can't reach the -1.
Two negatives. [-2, -3] gives 6 and [-1, -1, -1] gives 1: the best subarray is the first two elements, since the third -1 would make the product negative again.
Keeping only the maximum. Without minHere and the swap, [-2, 3, -4] gives 3 instead of 24, because the -6 that becomes 24 is thrown away.
Swapping after the update. The swap must come before maxHere and minHere are multiplied, or the flip for a negative element is applied one step late.
Forgetting the fresh start. The candidate nums(i) alone is what lets the product recover after a 0, or after a run that went badly negative. Using only maxHere * nums(i) would carry a 0 forward forever.

Testing

Results from running the solution:

`nums`	Result
`[2, 3, -2, 4]`	6
`[-2, 0, -1]`	0
`[-2, 3, -4]`	24
`[-3]`	-3
`[0]`	0
`[-2, -3]`	6
`[2, -5, -2, -4, 3]`	24
`[-1, -1, -1]`	1
`[1, -1, 0, 5]`	5

Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free