Changing one cell changed both rows. Why? [0] * 3 makes one row. Then [row] * 2 makes a list holding the same row object twice, not two separate rows. Both entries point to the same list in memory. Changing it through one name shows through the other.
Numbers are safe to repeat with *, because a number cannot be changed in place. Lists can be changed, so repeating a list repeats the same list. The fix is to build each row separately.
python
good = [[0] * 3 for _ in range(2)] # a new row each time round the loopgood[0][0] = 9print(good) # → [[9, 0, 0], [0, 0, 0]]
This bug is worth naming in any interview that involves a grid. It shows you understand how Python stores lists.
The transpose flips the matrix across its main diagonal, the line from top-left to bottom-right. Row r becomes column r. So the value at m[r][c] moves to t[c][r]. A 2 × 3 matrix becomes 3 × 2.
1 2 3 1 44 5 6 → 2 5 3 6
python
def transpose(m: list[list[int]]) -> list[list[int]]: rows, cols = len(m), len(m[0]) t = [[0] * rows for _ in range(cols)] # (1) for r in range(rows): for c in range(cols): t[c][r] = m[r][c] # (2) return tprint(transpose([[1, 2, 3], [4, 5, 6]])) # → [[1, 4], [2, 5], [3, 6]]
(1) The result has cols rows and rows columns. The shape flips.
(2) Row and column swap places.
The Python one-liner is [list(row) for row in zip(*m)]. zip(*m) hands zip every row as a separate argument. zip then pairs up the first items of every row, then the second items, and so on. Those groups are exactly the columns.
A square matrix keeps its shape when transposed, so it can be done without a new grid. Swap each element above the diagonal with its mirror below.
python
def transpose_square(m: list[list[int]]) -> None: n = len(m) for r in range(n): for c in range(r + 1, n): # (1) m[r][c], m[c][r] = m[c][r], m[r][c]sq = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]transpose_square(sq)print(sq) # → [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
(1) Start c at r + 1. Then each pair is visited once, from the upper side only. If c started at 0, every pair would be swapped twice, which puts everything back where it started. That is the classic bug: the code runs and the matrix comes out unchanged.
Transpose followed by reversing each row rotates a square matrix 90° clockwise. That is 4.28.1 Rotate Image.
Matrix multiplication is not cell by cell. Each cell of the result combines a whole row of the first matrix with a whole column of the second. Multiply them pair by pair and add up.
C[i][j] = \sum_{k} A[i][k] \times B[k][j]
Read it aloud: "cell i, j of the result is the sum, over every k, of row i's k-th value times column j's k-th value."
For that to work, a row of A and a column of B must be the same length. So the number of columns of A must equal the number of rows of B. An m \times p matrix times a p \times n matrix gives an m \times n matrix.
Why is it defined this odd way? A matrix describes a change to a list of numbers. A rotation of a picture is one example. Multiplying two matrices gives the single matrix that does both changes, one after the other. Row-times-column is exactly what makes that true. Volume II, Part 4 explains it in full.
python
def multiply(a: list[list[int]], b: list[list[int]]) -> list[list[int]]: m, p, n = len(a), len(b), len(b[0]) if len(a[0]) != p: raise ValueError("columns of a must equal rows of b") # (1) c = [[0] * n for _ in range(m)] for i in range(m): # (2) each row of a for j in range(n): # (3) each column of b total = 0 for k in range(p): # (4) walk along both together total += a[i][k] * b[k][j] c[i][j] = total return cprint(multiply([[1, 2], [3, 4]], [[5, 6], [7, 8]])) # → [[19, 22], [43, 50]]print(multiply([[1, 2, 3]], [[1], [2], [3]])) # → [[14]]
(1) Check the shapes first. Multiplying mismatched shapes would crash with an IndexError part way through, or worse, silently use the wrong numbers.
(2) Pick a row of the result.
(3) Pick a column of the result.
(4)k moves along row i of a and down column j of b at the same time. Each step multiplies one pair.
The second example multiplies a 1 × 3 by a 3 × 1, giving a 1 × 1: 1 \times 1 + 2 \times 2 + 3 \times 3 = 14.
Order matters.A \times B is usually not equal to B \times A. Often only one of them is even allowed by the shapes. This is unlike ordinary numbers, and interviewers like to check that you know it.
The cost. Three nested loops of sizes m, n and p. For two n \times n matrices that is n^3 multiplications. For n = 1000, a billion. Cleverer methods exist. Volker Strassen showed in 1969 that you can do it in about n^{2.81}. In real code, a library like NumPy runs this on fast, hand-tuned machine code, thousands of times faster than Python loops.
The main diagonal runs top-left to bottom-right. Its cells have r == c. The other diagonal runs top-right to bottom-left. Its cells have r + c == n - 1.
python
def diagonal_sum(m: list[list[int]]) -> int: n = len(m) total = 0 for i in range(n): total += m[i][i] # main diagonal total += m[i][n - 1 - i] # other diagonal if n % 2 == 1: total -= m[n // 2][n // 2] # (1) return totalprint(diagonal_sum([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # → 25
(1) When n is odd, the two diagonals cross in the centre cell. It was added twice, so take it off once. For the 3 × 3 example: main 1 + 5 + 9, other 3 + 5 + 7, total 30, minus the centre 5, gives 25.
This is LeetCode 1572. Spiral order, a common follow-up, is 4.28.2.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"What does [[0] * 3] * 2 do?" It makes one row and puts that same row in the list twice. Changing one row changes both. Build each row on its own: [[0] * 3 for _ in range(2)].
"Your in-place transpose gives back the same matrix. Why?" The inner loop probably starts at 0. Then each pair is swapped twice, which puts it back. Start the inner loop at r + 1.
"When can two matrices be multiplied?" When the number of columns of the first equals the number of rows of the second. The answer has the rows of the first and the columns of the second.
"Is A \times B the same as B \times A?" Usually not. Often only one of the two is even allowed by the shapes.
"How fast is matrix multiplication?" The simple method is O(n^3) for two n \times n matrices. Faster methods exist, starting with Strassen's in 1969.
One thing to volunteer: "In real code I would use NumPy's a @ b. It is many times faster than Python loops."
Next:4.0.24 Bubble Sort. The first of the seven sorting algorithms every computer-science course teaches.