Matrix Chain Multiplication

Hard
1602.

Matrix Chain Multiplication

Matrix Chain Multiplication is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Flipkart interviews.

You are given an array arr of length n describing a chain of n - 1 matrices: matrix i (0-indexed) has arr[i] rows and arr[i + 1] columns, so neighbouring matrices can always be multiplied.

Multiplying a p x q matrix by a q x r matrix costs p * q * r scalar multiplications. Matrix multiplication is associative, so the product of the whole chain is the same however it is parenthesised — but the cost is not.

Return the minimum number of scalar multiplications needed to compute the product of the whole chain. A chain of a single matrix costs 0.

Example 1

Input
arr = [40,20,30,10,30]
Output
26000
Explanation
Four matrices A (40x20), B (20x30), C (30x10), D (10x30). The order (A(BC))D costs 20*30*10 + 40*20*10 + 40*10*30 = 6000 + 8000 + 12000 = 26000, the cheapest.

Example 2

Input
arr = [10,20,30]
Output
6000
Explanation
Two matrices, one way to multiply them: 10 * 20 * 30.

Example 3

Input
arr = [5,7]
Output
0
Explanation
A single matrix needs no multiplication.

Constraints

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100 (so the answer fits in a 32-bit integer)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var matrixMultiplication = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Matrix Chain Multiplication — Solution in Python, Java & C++

Matrix Chain Multiplication solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Matrix Chain Multiplication is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Flipkart interviews.

Problem statement

You are given an array arr of length n describing a chain of n - 1 matrices: matrix i (0-indexed) has arr[i] rows and arr[i + 1] columns, so neighbouring matrices can always be multiplied.

Multiplying a p x q matrix by a q x r matrix costs p * q * r scalar multiplications. Matrix multiplication is associative, so the product of the whole chain is the same however it is parenthesised — but the cost is not.

Return the minimum number of scalar multiplications needed to compute the product of the whole chain. A chain of a single matrix costs 0.

Example 1

Input: arr = [40,20,30,10,30]
Output: 26000
Explanation: Four matrices A (40x20), B (20x30), C (30x10), D (10x30). The order (A(BC))D costs 20*30*10 + 40*20*10 + 40*10*30 = 6000 + 8000 + 12000 = 26000, the cheapest.

Example 2

Input: arr = [10,20,30]
Output: 6000
Explanation: Two matrices, one way to multiply them: 10 * 20 * 30.

Example 3

Input: arr = [5,7]
Output: 0
Explanation: A single matrix needs no multiplication.

Constraints

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100 (so the answer fits in a 32-bit integer)

Hints for Matrix Chain Multiplication

  1. Hint 1

    The last multiplication performed splits the chain into a left part and a right part, each computed on its own first.

  2. Hint 2

    Let cost[i][j] be the cheapest way to multiply matrices i..j. Try every split point k between them.

  3. Hint 3

    cost[i][j] = min over k of cost[i][k] + cost[k+1][j] + arr[i] * arr[k+1] * arr[j+1]. Fill it by increasing chain length so both halves are ready.

How to solve Matrix Chain Multiplication

Whatever the parenthesisation, there is one final multiplication that joins the product of matrices i..k with the product of k+1..j. Its cost depends only on the outer dimensions arr[i] * arr[k+1] * arr[j+1], and the two halves are independent sub-problems — classic interval DP.

Approach

  1. Let m = n - 1 be the number of matrices and cost[i][i] = 0.
  2. For chain lengths len = 2 … m, for every start i with j = i + len - 1, set cost[i][j] to the minimum over k = i … j - 1 of cost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1].
  3. Return cost[0][m - 1].

Why it works

An optimal order for i..j has some last split k, and the orders it uses inside each half must themselves be optimal (otherwise replacing one would lower the total). The product of matrices i..k is an arr[i] x arr[k+1] matrix and that of k+1..j is arr[k+1] x arr[j+1], so the final step costs arr[i] * arr[k+1] * arr[j+1]. Every shorter interval is filled before a longer one needs it.

Complexity

  • Time — O(n^3)
  • Space — O(n^2)

Pitfalls

  • arr has one more entry than there are matrices — matrix i is arr[i] x arr[i+1].
  • Filling the table row by row from the top uses intervals that are not ready yet; iterate by length (or i downward).
  • With dimensions up to 100 the cost stays below 98 * 100^3, well inside 32 bits; the original problem's limit of 500 could overflow.

Reference solution

Python

from typing import List

def matrixMultiplication(arr: List[int]) -> int:
    m = len(arr) - 1
    cost = [[0] * m for _ in range(m)]
    for length in range(2, m + 1):
        for i in range(0, m - length + 1):
            j = i + length - 1
            best = None
            for k in range(i, j):
                cand = cost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1]
                if best is None or cand < best:
                    best = cand
            cost[i][j] = best
    return cost[0][m - 1]

Java

public static int matrixMultiplication(int[] arr) {
    int m = arr.length - 1;
    int[][] cost = new int[m][m];
    for (int len = 2; len <= m; len++) {
        for (int i = 0; i + len - 1 < m; i++) {
            int j = i + len - 1;
            int best = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cand = cost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1];
                if (cand < best) best = cand;
            }
            cost[i][j] = best;
        }
    }
    return cost[0][m - 1];
}

C++

int matrixMultiplication(vector<int>& arr) {
    int m = arr.size() - 1;
    vector<vector<int>> cost(m, vector<int>(m, 0));
    for (int len = 2; len <= m; len++) {
        for (int i = 0; i + len - 1 < m; i++) {
            int j = i + len - 1;
            int best = INT_MAX;
            for (int k = i; k < j; k++) {
                best = min(best, cost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1]);
            }
            cost[i][j] = best;
        }
    }
    return cost[0][m - 1];
}

JavaScript

var matrixMultiplication = function(arr) {
    var m = arr.length - 1;
    var cost = [];
    for (var r = 0; r < m; r++) cost.push(new Array(m).fill(0));
    for (var len = 2; len <= m; len++) {
        for (var i = 0; i + len - 1 < m; i++) {
            var j = i + len - 1;
            var best = Infinity;
            for (var k = i; k < j; k++) {
                var cand = cost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1];
                if (cand < best) best = cand;
            }
            cost[i][j] = best;
        }
    }
    return cost[0][m - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming