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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1001 <= arr[i] <= 100 (so the answer fits in a 32-bit integer)
Hints for Matrix Chain Multiplication
Hint 1
The last multiplication performed splits the chain into a left part and a right part, each computed on its own first.
Hint 2
Let
cost[i][j]be the cheapest way to multiply matricesi..j. Try every split pointkbetween them.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
- Let
m = n - 1be the number of matrices andcost[i][i] = 0. - For chain lengths
len = 2 … m, for every startiwithj = i + len - 1, setcost[i][j]to the minimum overk = i … j - 1ofcost[i][k] + cost[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1]. - 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
arrhas one more entry than there are matrices — matrixiisarr[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
idownward). - 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