2-D arrays (matrices)

Rows and columns

A 2-D array, or matrix, is a grid. Rows run across, columns run down. A grid with m rows and n columns has m × n cells. In Python it is a list of rows, and each row is a list, so grid[r][c] is the cell in row r and column c. len(grid) is the number of rows and len(grid[0]) is the number of columns (when there is at least one row).

bad = [[0] * 3] * 2
bad[0][0] = 1
print(bad)    # Output: [[1, 0, 0], [1, 0, 0]]

good = [[0] * 3 for _ in range(2)]
good[0][0] = 1
print(good)   # Output: [[1, 0, 0], [0, 0, 0]]

Row-major traversal and neighbours

Row-major order means reading the grid row by row, left to right, like reading a page. It is the natural nested loop: for r in range(m), then for c in range(n). Visiting every cell is O(m × n). Many grid problems also look at the four neighbours of a cell (up, down, left, right); always check that r and c stay inside 0..m − 1 and 0..n − 1 before reading.

grid = [[1, 2, 3],
        [4, 5, 6]]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        print(grid[r][c], end=" ")
# Output: 1 2 3 4 5 6

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # up, down, left, right

Transpose

Transposing swaps rows and columns: the cell at (r, c) moves to (c, r). An m × n matrix becomes n × m, so a non-square matrix needs a NEW grid. zip(*grid) is a Python shortcut that groups the first items of every row, then the second items, and so on; it gives tuples, so convert each to a list.

grid = [[1, 2, 3],
        [4, 5, 6]]
t = [list(col) for col in zip(*grid)]
print(t)   # Output: [[1, 4], [2, 5], [3, 6]]

Rotate 90° clockwise

A clockwise rotation is a transpose followed by reversing each row. For a square n × n matrix both steps can be done in place (swap grid[r][c] with grid[c][r] for c > r, then reverse each row), O(n²) time and O(1) extra space. For a non-square matrix, build a new grid: rotated row c is column c read from bottom to top.

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]
rotated = [list(row) for row in zip(*grid[::-1])]
print(rotated)   # Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Spiral order

Spiral order reads the outer ring clockwise (top row, right column, bottom row, left column), then the next ring inside, and so on. Keep four boundaries: top, bottom, left and right. After reading the top row, move top down; after the right column, move right left; and so on. Before reading the bottom row and left column, check that top ≤ bottom and left ≤ right again, otherwise a single row or column is read twice. O(m × n) time.

Searching a sorted matrix

If every row is sorted left to right and every column is sorted top to bottom, start at the top-right corner. If the value there is bigger than the target, the whole column below is even bigger, so move left. If it is smaller, the whole row to the left is even smaller, so move down. Each step removes a row or a column, so the search takes at most m + n steps: O(m + n) time and O(1) space. This is called the staircase search.

Grids as maps

Many problems hide a grid: a cinema seat map, a chessboard of 8 × 8 squares, a maze where "#" is a wall, or pixels of an image. Counting islands of land or finding the shortest path through a maze is grid traversal with BFS or DFS, which you will learn in Module 9.

Common mistakes

• Creating rows with [[0] * n] * m, which shares one row. Fix: use a list comprehension.
• Mixing up rows and columns, for example grid[x][y] with x as the column. Fix: always name them r and c and write grid[r][c].
• Assuming the matrix is square. Fix: use m = len(grid) and n = len(grid[0]) separately, and test a 2 × 3 case.
• Crashing on [] or [[]]. Fix: check if not grid or not grid[0] first.
• Reading a single middle row or column twice in spiral order. Fix: re-check the boundaries before the bottom row and the left column.