Matrix Chain Multiplication in DSA Typescript

Mental Model

We want to find the best way to multiply a chain of matrices so that the total number of multiplications is as small as possible.

Analogy: Imagine you have several boxes to stack, and the order you stack them affects how much effort it takes. Choosing the right order saves a lot of work.

Matrices: A1(10x30) -> A2(30x5) -> A3(5x60)
Goal: Find best order to multiply A1 x A2 x A3

Chain: [10, 30, 5, 60]
Each number is a dimension between matrices

Initial:
A1(10x30) -> A2(30x5) -> A3(5x60) -> null

Dry Run Walkthrough

Input: matrices dimensions: [10, 30, 5, 60]

Goal: Find the minimum number of scalar multiplications needed to multiply A1 x A2 x A3

Step 1: Calculate cost of multiplying A1 and A2 first

Cost = 10 x 30 x 5 = 1500 multiplications

Why: We try one way to parenthesize to see the cost

Step 2: Calculate cost of multiplying A2 and A3 first

Cost = 30 x 5 x 60 = 9000 multiplications

Why: Try the other way to parenthesize to compare costs

Step 3: Calculate total cost if multiply (A1xA2) then multiply result with A3

Total cost = 1500 + (10 x 5 x 60) = 1500 + 3000 = 4500

Why: After first multiplication, multiply the result with A3

Step 4: Calculate total cost if multiply A1 with (A2xA3)

Total cost = 9000 + (10 x 30 x 60) = 9000 + 18000 = 27000

Why: After second multiplication, multiply A1 with the result

Step 5: Compare both total costs and choose minimum

Minimum cost = 4500 multiplications by multiplying (A1xA2) first

Why: We want the least number of multiplications

Result:

Minimum multiplication cost = 4500

Annotated Code

DSA Typescript

class MatrixChainMultiplication {
  static matrixChainOrder(p: number[]): number {
    const n = p.length - 1;
    const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

    for (let L = 2; L <= n; L++) {
      for (let i = 0; i <= n - L; i++) {
        const j = i + L - 1;
        m[i][j] = Number.MAX_SAFE_INTEGER;
        for (let k = i; k < j; k++) {
          const cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
          if (cost < m[i][j]) {
            m[i][j] = cost;
          }
        }
      }
    }
    return m[0][n - 1];
  }
}

// Driver code
const dimensions = [10, 30, 5, 60];
const minCost = MatrixChainMultiplication.matrixChainOrder(dimensions);
console.log(minCost);

for (let L = 2; L <= n; L++) {

increase chain length from 2 to n

for (let i = 0; i <= n - L; i++) {

set start index of chain

const j = i + L - 1;

set end index of chain

m[i][j] = Number.MAX_SAFE_INTEGER;

initialize minimum cost for this chain segment

for (let k = i; k < j; k++) {

try all possible split points

const cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];

calculate cost of splitting at k

if (cost < m[i][j]) { m[i][j] = cost; }

update minimum cost if current split is cheaper

return m[0][n - 1];

return minimum cost for full chain

Output

4500

Complexity Analysis

Time: O(n^3) because we check all chain lengths, start points, and split points

Space: O(n^2) because we store minimum costs for all subchains in a 2D table

vs Alternative: Naive approach tries all parenthesizations recursively with exponential time; dynamic programming reduces it to polynomial time

Edge Cases

Only one matrix (e.g., [10, 20])

No multiplication needed, cost is zero

DSA Typescript

const n = p.length - 1;

Two matrices (e.g., [10, 20, 30])

Direct multiplication cost calculated without splits

DSA Typescript

for (let L = 2; L <= n; L++) {

Matrices with same dimensions (e.g., [10, 10, 10, 10])

Algorithm still finds minimum cost correctly

DSA Typescript

if (cost < m[i][j]) { m[i][j] = cost; }

When to Use This Pattern

When you see a problem asking for the best way to multiply a sequence of matrices with minimal cost, use the Matrix Chain Multiplication pattern because it optimizes the order of operations.

Common Mistakes

Mistake: Confusing matrix dimensions and using wrong indices for cost calculation
Fix: Use p[i] * p[k+1] * p[j+1] for cost calculation to match matrix dimensions correctly

Mistake: Not initializing the cost table properly leading to incorrect minimum cost
Fix: Initialize m[i][j] to a very large number before checking splits

Summary

Finds the minimum number of scalar multiplications needed to multiply a chain of matrices.

Use when you want to multiply multiple matrices efficiently by choosing the best order.

The key insight is that the problem can be broken into smaller subproblems and solved using dynamic programming.

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

A. To find the maximum number of matrices that can be multiplied

B. To multiply all matrices in the chain directly without optimization

C. To count the total number of matrices in the chain

D. To find the minimum number of scalar multiplications needed to multiply a chain of matrices

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices to minimize cost.

2. Step 2: Identify what is minimized

   The cost minimized is the number of scalar multiplications, not the number of matrices or direct multiplication.

3. Final Answer:

   To find the minimum number of scalar multiplications needed to multiply a chain of matrices -> Option D

4. Quick Check:

   Goal = minimum scalar multiplications [OK]

Hint: Remember: minimize multiplication cost, not count matrices [OK]

Common Mistakes:

• Confusing multiplication count with matrix count
• Thinking the problem multiplies matrices directly
• Assuming maximum matrices multiplication is the goal

2. Which of the following is the correct TypeScript function signature for a recursive Matrix Chain Multiplication function that takes an array of matrix dimensions?

easy

A. function matrixChainOrder(dimensions: string): number

B. function matrixChainOrder(dimensions: number): number[]

C. function matrixChainOrder(dimensions: number[]): number

D. function matrixChainOrder(dimensions: number[][]): void

Solution

1. Step 1: Identify input type for matrix dimensions

   Matrix dimensions are given as an array of numbers representing sizes, so number[] is correct.

2. Step 2: Identify return type for minimum cost

   The function returns the minimum number of scalar multiplications, which is a number.

3. Final Answer:

   function matrixChainOrder(dimensions: number[]): number -> Option C

4. Quick Check:

   Input = number[], Output = number [OK]

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

Common Mistakes:

• Using string instead of number array for dimensions
• Returning an array instead of a number
• Using 2D array or void return incorrectly

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

function matrixChainOrder(p: number[]): number {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  for (let L = 2; L <= n; L++) {
    for (let i = 0; i < n - L + 1; i++) {
      const j = i + L - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

console.log(matrixChainOrder([10, 20, 30, 40]));

medium

A. 18000

B. 24000

C. 30000

D. 60000

Solution

1. Step 1: Understand the input and matrix dimensions

   The input array [10, 20, 30, 40] represents matrices of dimensions 10x20, 20x30, and 30x40.

2. Step 2: Calculate minimum multiplication cost

   Possible parenthesizations:
   - (A1 x (A2 x A3)) = 20*30*40 + 10*20*40 = 24000 + 8000 = 32000
   - ((A1 x A2) x A3) = 10*20*30 + 10*30*40 = 6000 + 12000 = 18000 (minimum)

3. Final Answer:

   18000 -> Option A

4. Quick Check:

   Minimum multiplications = 18000 [OK]

Hint: Check all splits and pick minimum cost [OK]

Common Mistakes:

• Calculating cost for only one parenthesization
• Mixing matrix dimensions order
• Forgetting to add multiplication costs correctly

4. Identify the error in the following TypeScript code snippet for Matrix Chain Multiplication and select the fix:

function matrixChainOrder(p: number[]): number {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
  for (let L = 2; L <= n; L++) {
    for (let i = 0; i < n - L + 1; i++) {
      const j = i + L - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k] * p[j];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

medium

A. Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1]

B. Initialize m with Infinity instead of 0

C. Change loop for (let k = i; k <= j; k++) to k < j

D. Return m[0][n] instead of m[0][n - 1]

Solution

1. Step 1: Identify the multiplication cost formula error

   The cost formula uses incorrect indices: p[i] * p[k] * p[j] should use p[k + 1] and p[j + 1] to represent matrix dimensions correctly.

2. Step 2: Confirm other parts are correct

   Initialization with 0 is correct for diagonal, loop ranges are correct, and return index is correct.

3. Final Answer:

   Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1] -> Option A

4. Quick Check:

   Correct cost formula indices fix error [OK]

Hint: Check matrix dimension indices carefully in cost formula [OK]

Common Mistakes:

• Using wrong indices for matrix dimensions in cost calculation
• Changing loop bounds unnecessarily
• Returning wrong matrix cell

5. Given matrices with dimensions [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the Matrix Chain Multiplication approach.

hard

A. 1510

B. 2010

C. 4050

D. 3500

Solution

1. Step 1: Understand matrix dimensions and chain length

   The array represents matrices: 5x10, 10x3, 3x12, 12x5, 5x50, 50x6 (6 matrices).

2. Step 2: Use dynamic programming to find minimum cost

   By calculating all splits and costs:
   - Minimum cost found is 2010 scalar multiplications.

3. Final Answer:

   2010 -> Option B

4. Quick Check:

   Minimum scalar multiplications = 2010 [OK]

Hint: Use DP table to check all splits and pick minimum [OK]

Common Mistakes:

• Calculating only one split option
• Mixing up matrix dimensions order
• Forgetting to add multiplication costs for subproblems