Problem overview
maxProduct receives an array of integers, nums, and returns the largest product of a subarray. A subarray is a run of one or more elements that stand next to each other, and its product is all its elements multiplied together. Elements may be negative or zero.
For [2, 3, -2, 4] the answer is 6, from the subarray [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. The pair -2, -1 would give 2, but it isn't a subarray, since the 0 stands between them. For [-2, 3, -4] the whole array wins with 24, because the two negatives cancel.
The statement asks for O(n) time and O(1) extra space.
Approach: track the largest and the smallest product
Trying every start and end is O(n²) subarrays. A single pass works if we know, at each element, the best product of a subarray that ends there. The best subarray overall ends somewhere, so the largest of these values is the answer.
For a sum, the best subarray ending at i is the best one ending at i - 1 extended by nums[i], or nums[i] alone. A product has a catch: a negative number flips the order. The most negative product ending at i - 1, multiplied by a negative nums[i], becomes the largest. So we keep two numbers at each step:
maxHere, the largest product of a subarray ending at the current element;minHere, the smallest (most negative) one.
When the current element is negative, we swap the two before multiplying, so each is the right one to extend. Then each is updated with the same two choices: start fresh at the current element, or extend the run. Starting fresh is also how a run gets past a zero: after a 0, the product of any extended run is 0, while starting fresh keeps the next element's own value.
Step by step
- Three variables, all
letand all starting atnums[0]:maxHere,minHereandresult, the largest product found so far. At the first element, the only subarray ending there is the element itself, so even a negative first element is a valid start forresult. - The loop.
igoes from 1 whilei < nums.length, because element 0 is already counted. - Swap on a negative. If
nums[i] < 0, swap with the destructuring assignment[maxHere, minHere] = [minHere, maxHere]. - Update the maximum:
maxHere = Math.max(nums[i], maxHere * nums[i]). - Update the minimum:
minHere = Math.min(nums[i], minHere * nums[i]). - Update the answer:
result = Math.max(result, maxHere). - Return
result.
The solution in TypeScript
class Solution {
maxProduct(nums: number[]): number {
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;
}
}
TypeScript details
let maxHere = nums[0];needs no annotation: TypeScript infersnumberfromnums[0]. It isletbecause the loop changes it.[maxHere, minHere] = [minHere, maxHere];builds an array of the two current values and unpacks it back in the other order, which swaps the variables without a temporary one. The right side is evaluated completely before either variable changes.numberis a double, so there is no integer overflow. The statement guarantees that every subarray product fits in 32 bits, so the values here are exact.- Products with zero can produce
-0inside the loop (for example-2 * 0is-0).Math.maxtreats0as larger than-0, and the function returns0for the lesson's zero cases. - Types are erased when the code compiles to JavaScript. Nothing checks at run time that
numsholds numbers, or that it has at least one element: an empty array would makenums[0]undefined.
Tracing examples
Printing the variables after each step of the loop gives these values.
For [-2, 3, -4] (start: all three variables are -2):
i | nums[i] | maxHere | minHere | result |
|---|---|---|---|---|
| 1 | 3 | 3 | -6 | 3 |
| 2 | -4 | 24 | -12 | 24 |
At i = 2, the element is negative, so the variables swap first: maxHere becomes -6 and minHere becomes 3. Then -6 * -4 gives 24, the new maximum.
For [2, 3, -2, 4] (start: all three variables are 2):
i | nums[i] | maxHere | minHere | result |
|---|---|---|---|---|
| 1 | 3 | 6 | 3 | 6 |
| 2 | -2 | -2 | -12 | 6 |
| 3 | 4 | 4 | -48 | 6 |
Here the negative element ends the good run: at i = 2 every subarray ending at -2 is negative, and maxHere is just -2. The answer, 6, was already recorded in result.
Complexity
Time: O(n). One pass with constant work per element.
Space: O(1). Only the three variables are kept.
Edge cases and common mistakes
- Tracking only the maximum. Without
minHereand the swap,[-2, 3, -4]gives 6 instead of 24: the large negative product that a later negative would turn positive is lost. - Zeros split the array. A subarray containing a 0 has product 0. The "start fresh" choice,
nums[i]alone, lets both variables recover after a zero. For[-2, 0, -1]the result is 0. - All negative numbers. The answer can be negative when the array is a single negative number:
[-2]returns -2. That is whyresultstarts atnums[0]and not at 0. - Starting
resultat 0. That would be wrong for[-2], since a subarray needs at least one element. - Two negatives in a row.
[-1, -1]returns 1, and[-2, -3, -4]returns 12 (the last two elements). - Using
result = maxHereat the end. The best subarray may end before the last element, as in[2, 3, -2, 4], soresultmust keep the best seen so far.
Testing
Running maxProduct on a few arrays gives:
nums | Result |
|---|---|
[2,3,-2,4] | 6 |
[-2,0,-1] | 0 |
[-2,3,-4] | 24 |
[-2] | -2 |
[0,2] | 2 |
[2,-5,-2,-4,3] | 24 |
[1,-2,0,3] | 3 |
[-2,-3,-4] | 12 |
