Maximum Product Subarray in DSA Typescript

Mental Model

We want to find the largest product of a continuous part of the list. Because negative numbers can flip the sign, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on a slippery stone (negative number) can flip your direction. To find the farthest point you can reach, you remember both your farthest forward and backward steps because a backward step might help you jump forward later.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5]
Track maxProd and minProd at each step to handle sign flips.

Dry Run Walkthrough

Input: array: [2, -3, 4, -1, 0, 5]

Goal: Find the maximum product of any continuous subarray

Step 1: Start with first element: maxProd = 2, minProd = 2, result = 2

maxProd=2, minProd=2, result=2

Why: Initialize with first element to start tracking products

Step 2: Process -3: swap maxProd and minProd because -3 is negative; maxProd = max(-3, 2 * -3) = -3; minProd = min(-3, 2 * -3) = -6; update result = max(2, -3) = 2

maxProd=-3, minProd=-6, result=2

Why: Negative flips max and min, so swap to keep track correctly

Step 3: Process 4: maxProd = max(4, -3 * 4) = 4; minProd = min(4, -6 * 4) = -24; update result = max(2, 4) = 4

maxProd=4, minProd=-24, result=4

Why: Positive number updates max and min normally

Step 4: Process -1: swap maxProd and minProd; maxProd = max(-1, -24 * -1) = 24; minProd = min(-1, 4 * -1) = -4; update result = max(4, 24) = 24

maxProd=24, minProd=-4, result=24

Why: Negative flips max and min again, possibly increasing max product

Step 5: Process 0: maxProd = max(0, 24 * 0) = 0; minProd = min(0, -4 * 0) = 0; update result = max(24, 0) = 24

maxProd=0, minProd=0, result=24

Why: Zero resets product, so start fresh from next element

Step 6: Process 5: maxProd = max(5, 0 * 5) = 5; minProd = min(5, 0 * 5) = 0; update result = max(24, 5) = 24

maxProd=5, minProd=0, result=24

Why: Positive number updates max product, but result remains max so far

Result:

Maximum product subarray is 24

Annotated Code

DSA Typescript

class Solution {
  maxProduct(nums: number[]): number {
    if (nums.length === 0) return 0;
    let maxProd = nums[0];
    let minProd = nums[0];
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
      const num = nums[i];
      if (num < 0) {
        // Swap maxProd and minProd because negative flips sign
        [maxProd, minProd] = [minProd, maxProd];
      }
      maxProd = Math.max(num, maxProd * num); // max product ending here
      minProd = Math.min(num, minProd * num); // min product ending here
      result = Math.max(result, maxProd); // update global max
    }
    return result;
  }
}

// Driver code
const solution = new Solution();
const input = [2, -3, 4, -1, 0, 5];
console.log(solution.maxProduct(input));

if (num < 0) { [maxProd, minProd] = [minProd, maxProd]; }

Swap max and min when current number is negative to handle sign flip

maxProd = Math.max(num, maxProd * num);

Calculate max product ending at current position

minProd = Math.min(num, minProd * num);

Calculate min product ending at current position

result = Math.max(result, maxProd);

Update global maximum product found so far

Output

24

Complexity Analysis

Time: O(n) because we scan the array once, updating max and min products at each step

Space: O(1) because we use only a few variables to track products and result

vs Alternative: Naive approach tries all subarrays with O(n^2) or O(n^3) time, which is much slower

Edge Cases

Empty array

Returns 0 immediately

DSA Typescript

if (nums.length === 0) return 0;

Array with one element

Returns that element as max product

DSA Typescript

let maxProd = nums[0];

Array with zeros

Zeros reset product calculation, handled naturally by max/min updates

DSA Typescript

maxProd = Math.max(num, maxProd * num);

When to Use This Pattern

When asked to find the maximum product of a continuous subarray, especially with negative numbers, use the max/min tracking pattern to handle sign flips efficiently.

Common Mistakes

Mistake: Not swapping max and min products when encountering a negative number
Fix: Add a swap of maxProd and minProd before updating them when current number is negative

Summary

Finds the maximum product of any continuous subarray in a list.

Use when you need the largest product subarray and the array can have negative numbers and zeros.

Keep track of both maximum and minimum products at each step because negatives can flip the sign.

Practice

1. What does the "Maximum Product Subarray" problem ask you to find in an array of integers?

easy

A. The subarray with the largest sum of its elements

B. The contiguous subarray with the largest product of its elements

C. The longest subarray with all positive numbers

D. The subarray with the smallest product of its elements

Solution

1. Step 1: Understand the problem statement

   The problem asks for a contiguous part of the array where the product of all numbers is as large as possible.

2. Step 2: Differentiate from similar problems

   This is different from finding the largest sum or smallest product; it specifically focuses on the product of elements in a continuous segment.

3. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option B

4. Quick Check:

   Maximum product subarray means largest product segment [OK]

Hint: Look for continuous elements with max product, not sum [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring that subarray must be contiguous
• Thinking about longest subarray instead of max product

2. Which of the following TypeScript function signatures correctly represents a function to find the maximum product subarray?

easy

A. function maxProduct(nums: number[]): number

B. function maxProduct(nums: string): number

C. function maxProduct(nums: number): number[]

D. function maxProduct(nums: number[]): string

Solution

1. Step 1: Check input parameter type

   The input should be an array of numbers, so nums: number[] is correct.

2. Step 2: Check return type

   The function returns the maximum product value, which is a number, not an array or string.

3. Final Answer:

   function maxProduct(nums: number[]): number -> Option A

4. Quick Check:

   Input array, output number matches signature [OK]

Hint: Input is number array, output is single number [OK]

Common Mistakes:

• Using string type for input or output
• Returning array instead of number
• Incorrect parameter types

3. What is the output of the following TypeScript code?

function maxProduct(nums: number[]): number {
  let maxProd = nums[0];
  let minProd = nums[0];
  let result = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
      [maxProd, minProd] = [minProd, maxProd];
    }
    maxProd = Math.max(nums[i], maxProd * nums[i]);
    minProd = Math.min(nums[i], minProd * nums[i]);
    result = Math.max(result, maxProd);
  }
  return result;
}

console.log(maxProduct([2, 3, -2, 4]));

medium

A. 6

B. 4

C. -2

D. 24

Solution

1. Step 1: Initialize variables and start loop

   maxProd, minProd, and result start at 2. Loop from index 1 to 3.

2. Step 2: Iterate and update maxProd, minProd, and result

   At i=1 (3): maxProd = max(3, 2*3)=6, minProd = min(3, 2*3)=3, result=6.
   At i=2 (-2): nums[i]<0, swap maxProd and minProd: maxProd=3, minProd=6.
   maxProd = max(-2, 3*(-2)) = max(-2, -6) = -2.
   minProd = min(-2, 6*(-2)) = min(-2, -12) = -12.
   result = max(6, -2) = 6.
   At i=3 (4): maxProd = max(4, -2*4) = max(4, -8) = 4.
   minProd = min(4, -12*4) = min(4, -48) = -48.
   result = max(6, 4) = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max product subarray is [2,3] = 6 [OK]

Hint: Track max and min products, swap on negative [OK]

Common Mistakes:

• Not swapping max and min on negative number
• Only tracking max product, ignoring min product
• Confusing max product with sum

4. Identify the bug in this TypeScript function for maximum product subarray:

function maxProduct(nums: number[]): number {
  let maxProd = 1;
  let minProd = 1;
  let result = Number.MIN_VALUE;
  for (let num of nums) {
    if (num < 0) {
      let temp = maxProd;
      maxProd = minProd;
      minProd = temp;
    }
    maxProd = Math.max(num, maxProd * num);
    minProd = Math.min(num, minProd * num);
    result = Math.max(result, maxProd);
  }
  return result;
}

medium

A. Initializing maxProd and minProd to 0 instead of 1

B. Not swapping maxProd and minProd when num is positive

C. Using a for loop instead of forEach

D. Using Number.MIN_VALUE instead of Number.NEGATIVE_INFINITY for result

Solution

1. Step 1: Understand Number.MIN_VALUE usage

   Number.MIN_VALUE is the smallest positive number close to zero, not the most negative number.

2. Step 2: Correct initialization for result

   To track maximum product correctly, result should start at Number.NEGATIVE_INFINITY to handle negative products properly.

3. Final Answer:

   Using Number.MIN_VALUE instead of Number.NEGATIVE_INFINITY for result -> Option D

4. Quick Check:

   Use Number.NEGATIVE_INFINITY for max tracking [OK]

Hint: Use Number.NEGATIVE_INFINITY for max initial value [OK]

Common Mistakes:

• Confusing Number.MIN_VALUE with negative infinity
• Not swapping max and min on negative number
• Wrong initial values for maxProd and minProd

5. Given the array [-1, -3, -10, 0, 60], what is the maximum product subarray and its product?

hard

A. Subarray: [-1, -3, -10], Product: -30

B. Subarray: [-3, -10, 0], Product: 0

C. Subarray: [60], Product: 60

D. Subarray: [-10, 0, 60], Product: 0

Solution

1. Step 1: Analyze subarrays and their products

   Check products of contiguous subarrays:
   [-1] = -1
   [-1, -3] = 3
   [-1, -3, -10] = -30
   [-3] = -3
   [-3, -10] = 30
   [-10] = -10
   [0] = 0
   [60] = 60

2. Step 2: Identify maximum product

   The largest product found is 60 from subarray [60].

3. Final Answer:

   Subarray: [60], Product: 60 -> Option C

4. Quick Check:

   Max product is 60 from single element [60] [OK]

Hint: Check single elements and negative pairs carefully [OK]

Common Mistakes:

• Assuming negative product is maximum
• Ignoring single element subarrays
• Confusing zero product with max product