Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 225 ยท Arrays and Lists

Matrices and 2D Arrays

Work with 2D arrays in Python: traversal orders, transpose, rotate 90 degrees, spiral order, diagonals, searching a sorted matrix and a grid neighbours helper.

A matrix (or 2D array, or grid) is a table of values with rows and columns. Images, game boards, maps, spreadsheets and the tables of dynamic programming are all matrices. In Python the usual representation is a list of lists: grid[r][c] is the value in row r, column c.

Matrix problems are rarely hard in theory; they are hard because of indexes. You juggle two coordinates, four directions and many edge cases. In this lesson you will build a small toolkit: build a grid correctly, traverse it in different orders, transpose and rotate it, walk a spiral, work with diagonals, search a sorted matrix in O(m + n), and write a reusable neighbours helper that you will use again for graph traversal on grids.

Before starting, make sure you are comfortable with plain arrays and Python lists, and with the cost of list operations from Array Operations.

Creating a grid (and the classic trap)

An m x n matrix has m rows and n columns. Memory-wise it is a list of m row-lists. The most common beginner bug is creating the rows with multiplication:

Python The shared-rows trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

[[0] * cols] * rows repeats a reference to one list, so changing one row changes them all. [0] * cols on its own is safe because integers are immutable. Always build rows with a comprehension. See Memory and Data Layout for why.

TEXT
        col 0  col 1  col 2  col 3
row 0 [   1      2      3      4  ]
row 1 [   5      6      7      8  ]
row 2 [   9     10     11     12  ]

grid[1][2] == 7        rows = 3, cols = 4

Traversal orders

The order you loop in matters for correctness (what you see first) and, in lower-level languages, for speed, because rows are stored contiguously (see cache locality). Python lists of lists do not benefit much, but the habit is good.

Python Row-major, column-major and boundaries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

zip(*grid) unpacks the rows as arguments, so zip pairs up the first elements, then the second elements and so on: it hands you the columns. It is the idiomatic Python transpose, and it is also our next topic.

Transpose

The transpose flips a matrix over its main diagonal: element (r, c) goes to (c, r). A 3x4 matrix becomes 4x3. For a square matrix you can do it in place by swapping each pair above the diagonal once.

Python Transpose: new matrix and in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(mn) for either; space O(mn) for the new matrix, O(1) for the in-place square version. If the inner loop started at c = 0 instead of r + 1, every pair would swap twice and you would get the original matrix back.

Rotate 90 degrees clockwise

A famous interview problem: rotate an n x n image by 90 degrees clockwise in place. The trick is to see a rotation as two simpler moves: transpose, then reverse every row.

TEXT
original      transpose     reverse each row (= rotated clockwise)
1 2 3         1 4 7         7 4 1
4 5 6   -->   2 5 8   -->   8 5 2
7 8 9         3 6 9         9 6 3

For a counter-clockwise rotation, reverse the rows first and then transpose (or transpose, then reverse the order of rows).

Python Rotate a square matrix in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The one-liner zip(*grid[::-1]) reverses the row order, then reads columns, which is exactly a clockwise rotation. It costs O(m*n) extra space, so use the two-step version when the problem demands in place.

Spiral order

Read the matrix in a clockwise spiral: top row left to right, right column downward, bottom row right to left, left column upward, then repeat on the inner layer. The standard method keeps four shrinking boundaries: top, bottom, left, right.

TEXT
 1  2  3  4          path: 1 2 3 4  8 12  11 10 9  5  6 7
 5  6  7  8
 9 10 11 12
Python Spiral order with four boundaries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two if guards are the part people forget. With a single row or column, the boundaries cross after the first half-pass, and without the guards you would visit cells twice. Every cell is visited exactly once: O(m*n) time, O(1) extra space besides the output.

Diagonals

Two cells are on the same main-direction diagonal (top-left to bottom-right) when r - c is equal. They are on the same anti-diagonal when r + c is equal. That single observation turns diagonal problems into grouping problems.

TEXT
r - c:   0 -1 -2        r + c:  0 1 2
         1  0 -1                1 2 3
         2  1  0                2 3 4
Python Diagonals by r-c and r+c

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same keys appear in the N-Queens puzzle: two queens attack along a diagonal exactly when r - c or r + c match.

Searching a sorted matrix

Suppose every row is sorted ascending and every column is sorted ascending (but a row's last element is not necessarily smaller than the next row's first). Find a target.

  • Brute force: check every cell, O(m*n).
  • Binary search per row: O(m log n).
  • Staircase search: start at the top-right corner. If the value equals the target, done. If it is larger than the target, nothing below it in this column can be smaller, so move left. If it is smaller, nothing to its left in this row can be bigger, so move down. Each step discards a whole row or column: O(m + n).
Python Staircase search in a row- and column-sorted matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If instead the matrix is fully sorted when read row by row (each row starts above the last value of the previous row), treat it as one sorted list of m*n elements and run a single binary search with row, col = divmod(mid, n): O(log(m*n)). See Binary Search.

A grid neighbours helper

Flood fill, islands, shortest paths in a maze and game of life all repeat the same code: visit the up/down/left/right neighbours that are inside the grid. Write it once.

Python Neighbours helper and a tiny flood fill

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using a direction list instead of four copy-pasted blocks removes a whole class of typos. Remember the bound check order: 0 <= nr < rows must come before you index the grid, or negative indexes silently wrap around in Python instead of raising an error.

In Python, grid[-1][0] is valid: it is the last row. A neighbour check that forgets nr >= 0 does not crash, it quietly reads from the opposite edge of the grid. Always test both bounds.

Determinant, adjoint, inverse and Strassen

Matrix algebra shows up in DSA when you count paths, solve linear recurrences or work with transformations. The classic exercises here follow from one definition, the determinant.

  • The minor M(i, j) of a square matrix is the determinant of the smaller matrix you get by deleting row i and column j.
  • The cofactor is C(i, j) = (-1)^(i + j) * M(i, j).
  • Cofactor expansion along the first row: det(A) = sum over j of A[0][j] * C(0, j). It is a recursive definition, and a direct implementation costs O(n!), so it is only for small matrices or for understanding.
  • The adjoint (adjugate) is the transpose of the matrix of cofactors.
  • If det(A) != 0, the inverse is adj(A) / det(A). If det(A) == 0 the matrix is singular and has no inverse.

For anything bigger than about 8 by 8, use elimination: Gaussian elimination computes a determinant in O(n^3) and can invert a matrix by reducing [A | I]. Use Fraction to keep results exact.

Python Cofactors, adjoint and inverse with exact fractions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Strassen's multiplication

Multiplying two n x n matrices with the three-loop definition costs O(n^3). Strassen's algorithm splits each matrix into four n/2 blocks and, with a clever choice of sums, needs only seven recursive block multiplications instead of eight. That is the recurrence T(n) = 7 T(n/2) + O(n^2), which solves to O(n^(log2 7)) โ‰ˆ O(n^2.81) (see recurrences for the master theorem). The seven products are:

TEXT
M1 = (A11 + A22)(B11 + B22)     C11 = M1 + M4 - M5 + M7
M2 = (A21 + A22) B11            C12 = M3 + M5
M3 = A11 (B12 - B22)            C21 = M2 + M4
M4 = A22 (B21 - B11)            C22 = M1 - M2 + M3 + M6
M5 = (A11 + A12) B22
M6 = (A21 - A11)(B11 + B12)
M7 = (A12 - A22)(B21 + B22)
Python Strassen versus the schoolbook product

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In Python, Strassen is slower than the plain method for ordinary sizes, because the extra additions and the recursion cost more than the saved multiplication. In real libraries it only pays off for large matrices (typically hundreds of rows) and it is less numerically stable with floating-point numbers. Treat it as a lesson about trading multiplications for additions, the same trade that makes Karatsuba multiplication fast.

Complexity summary

Task Time Extra space
Traverse every cell O(m*n) O(1)
Transpose (new matrix) O(m*n) O(m*n)
Rotate square in place O(nยฒ) O(1)
Spiral order O(m*n) O(1) besides output
Staircase search O(m + n) O(1)
Binary search, fully sorted O(log(m*n)) O(1)

Common mistakes

  • Swapping rows and columns. len(grid) is the number of rows, len(grid[0]) the number of columns. In grid[r][c], the first index is the row (vertical position, "y").
  • [[0]*n]*m. Shared rows. Use a comprehension.
  • Assuming a square matrix. Many problems give rectangles; transpose and rotate change the dimensions.
  • Empty input. grid[0] raises an IndexError when grid == []. Guard it.
  • Modifying while scanning. Game of Life needs the next state computed from the old state: copy the grid, or encode both states in one cell.
  • Negative index wrap-around when checking neighbours.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is wrong with grid = [[0] * 3] * 4?

    The outer multiplication repeats a reference to one inner list. Use [[0] * 3 for _ in range(4)] to get independent rows.
  2. 2. Which two steps rotate a square matrix 90 degrees clockwise?

    Transposing turns rows into columns and reversing each row then mirrors the result into a clockwise rotation.
  3. 3. In the staircase search of a row- and column-sorted matrix, why start at the top-right corner?

    At the top-right, the value is the largest in its row and the smallest in its column, so a comparison with the target removes one full row or column. That gives O(m + n).
  4. 4. Which values are equal for all cells on one anti-diagonal (top-right to bottom-left)?

    Moving down one row and left one column keeps r + c constant. Cells on a main diagonal share r - c instead.
  5. 5. Why must a neighbour check test nr >= 0 explicitly in Python?

    grid[-1] is the last row. Without the check you would read the wrong cell instead of getting an IndexError.

Summary

  • A matrix is a list of lists; grid[r][c] is row r, column c. Build rows with a comprehension, never [[0]*n]*m.
  • zip(*grid) gives the columns and is the idiomatic transpose.
  • Rotate a square clockwise in place by transposing, then reversing each row.
  • Spiral order uses four shrinking boundaries; guard the last two passes for single rows and columns.
  • Diagonals: r - c is constant on one direction, r + c on the other.
  • A sorted matrix can be searched in O(m + n) by the staircase method, or O(log(m*n)) if fully sorted.
  • Keep a direction list and a bounds-checked neighbours helper; always test both bounds.

Next: Strings in DSA, where the sequence is made of characters and immutability changes the rules.