Maximum Product Subarray in DSA Typescript - Execution Trace

Concept Flow - Maximum Product Subarray

Start

↓

Initialize maxProd, minProd, result with first element

↓

For each element from second to end

↓

Calculate candidates: current element, maxProd*current, minProd*current

↓

Update maxProd = max of candidates

↓

Update minProd = min of candidates

↓

Update result = max(result, maxProd)

↓

Repeat until end

↓

Return result

We scan the array once, keeping track of the maximum and minimum products ending at each position, updating the result with the highest max product found.

Execution Sample

DSA Typescript

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

Finds the maximum product of any contiguous subarray by tracking max and min products at each step.

Execution Table

Step	Current Element	Candidates [num, maxProd*num, minProd*num]	maxProd	minProd	Result	Visual State (Subarray contributing to maxProd)
0	nums[0] = 2	[2, -, -]	2	2	2	[2]
1	nums[1] = 3	[3, 2*3=6, 2*3=6]	6	3	6	[2,3]
2	nums[2] = -2	[-2, 6*(-2)=-12, 3*(-2)=-6]	-2	-12	6	[-2]
3	nums[3] = 4	[4, -2*4=-8, -12*4=-48]	4	-48	6	[4]
Exit	-	-	-	-	6	End of array, max product found is 6

💡 Reached end of array, final max product is 6

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
maxProd	2	6	-2	4	4
minProd	2	3	-12	-48	-48
result	2	6	6	6	6

Key Moments - 3 Insights

Why do we track both maxProd and minProd at each step?

Because a negative number can turn a small minProd into a large maxProd when multiplied, tracking both ensures we don't miss a larger product (see Step 2 in execution_table where minProd becomes -12).

Why do we update maxProd and minProd using the current element and their products?

Because the max or min product subarray ending at current index could be just the current element alone or extended by multiplying previous maxProd or minProd (see candidates in execution_table).

Why is the result updated only with maxProd and not minProd?

Because minProd is the smallest product (possibly negative), only maxProd can give the maximum product subarray value (see result column in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the value of minProd?

A -6

B -12

C -2

D 3

💡 Hint

Check the 'minProd' column at Step 2 in the execution_table.

At which step does the maxProd become less than the current element itself?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'maxProd' and 'Current Element' columns in execution_table to find when maxProd < current element.

If the array started with a negative number instead of 2, how would the initial maxProd and minProd be set?

A Both set to 0

B maxProd set to 0, minProd to negative number

C Both set to that negative number

D maxProd set to positive number, minProd to negative number

💡 Hint

Initial maxProd and minProd are always set to the first element of the array (see variable_tracker Start values).

Concept Snapshot

Maximum Product Subarray:
- Track maxProd and minProd at each index
- maxProd = max(current, maxProd*current, minProd*current)
- minProd = min(current, maxProd*current, minProd*current)
- Update result = max(result, maxProd)
- Handles negative numbers by tracking minProd
- Single pass, O(n) time complexity

Full Transcript

This visualization traces the Maximum Product Subarray algorithm. We start by initializing maxProd, minProd, and result with the first element. Then for each element, we calculate three candidates: the element itself, maxProd times the element, and minProd times the element. We update maxProd to the maximum of these, minProd to the minimum, and result to the maximum result so far. Tracking both maxProd and minProd is crucial because multiplying by a negative can flip minProd to maxProd. The execution table shows these values step-by-step for the array [2,3,-2,4], ending with a maximum product of 6. Key moments clarify why both maxProd and minProd are tracked and why result updates only with maxProd. The quiz tests understanding of these steps and initializations. This approach runs in one pass with O(n) time complexity.

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