DSA interview question

Matrix Chain Multiplication (Minimum Multiplications)

Hard · Algorithms · Topics: dynamic programming, mcm, partition

The problem

You're working on a rendering engine's transform pipeline. Every frame, the engine multiplies a chain of transformation matrices (model → world → view → projection, plus a few intermediate bone/skinning matrices) to get a final transform. Matrix multiplication is associative — ((AB)C)D gives the same result as A(B(CD)) — but the number of scalar multiplications needed depends heavily on the order you parenthesize the chain in.

Given an array dims of length n+1 representing n matrices, where matrix i has dimensions dims[i-1] x dims[i], find the minimum number of scalar multiplications needed to compute the full product.

Example: dims = [40, 20, 30, 10, 30] represents 4 matrices:

A1: 40x20
A2: 20x30
A3: 30x10
A4: 10x30

Find the cheapest parenthesization order.

Function signature

int matrixChainOrder(vector<int>& dims);

Test cases

Input `dims`	Output	Explanation
`[40, 20, 30, 10, 30]`	26000	Best split: `(A1(A2A3))A4` or similar — verify via DP table
`[10, 20, 30]`	6000	Only one way to multiply 2 matrices: `102030`
`[10, 20, 30, 40, 30]`	30000	Classic textbook example
`[1, 2, 3, 4]`	18	Small chain, verify by brute-force enumeration
`[5, 10]`	0	Single matrix — no multiplication needed
`[10]`	0	Degenerate — no matrices (edge case, handle gracefully)

(Always sanity check: dims.size() == n+1 for n matrices; a single matrix needs 0 multiplications.)

How interviewers phrase it

"You're given the dimensions of a chain of matrices. Find the minimum number of scalar multiplications needed to multiply them all together."
"Matrix multiplication is associative but not commutative — given the order matters for cost, find the optimal parenthesization."
Sometimes given as an array of matrix objects instead of a dims array — clarify the input format.

Clarifying questions to ask

Is the input given as an array of (rows, cols) pairs per matrix, or as a single dims array of length n+1? (Confirm the exact format before coding.)
Do I need to return just the minimum cost, or also the actual parenthesization (bracketing)?
Can n be large (checking if O(n³) DP is acceptable, or if I need to think about Catalan-number brute force being infeasible)?
Are matrix dimensions guaranteed to be compatible (i.e., is the chain always valid so consecutive matrices can multiply)?
Can any dimension be 0 or negative? (Edge case handling.)

Follow-ups to expect

"Can you print the actual optimal parenthesization, not just the cost?"
"What's the time and space complexity, and can you reduce space?"
"Why not brute-force all parenthesizations?"
"Can you solve this recursively with memoization first, then convert to tabulation?"
"How does this relate to other interval DP problems?"
"What if you wanted to minimize additions instead of multiplications, or minimize memory instead of cost?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview