Sorting & Comparators Bit Manipulation Basics

CATEGORY 9 OF 13

Matrix / 2D Basics

Build confidence with 2D arrays — learn matrix creation, row/column iteration, boundary checks, transposition, and rotation so grid-based problems feel routine.

Time: O(m x n) for full matrix traversal

Space: O(m x n) for matrix copy, O(1) for in-place operations

Learn & Reference

Understanding the Pattern

Matrix / 2D Basics

Two-dimensional arrays (matrices) model grids, game boards, images, and spreadsheets. Before tackling graph traversal or dynamic programming on grids, you need to be comfortable creating a matrix, addressing elements with [row][col], iterating in different orders, and performing basic transformations like transposition and rotation.

Creating a 2D Array

A matrix with m rows and n columns is an array of arrays. The critical mistake in many languages is accidentally sharing row references:

# WRONG in Python — all rows point to the same list:
matrix = [[0] * cols] * rows

# CORRECT — each row is a separate list:
matrix = [[0] * cols for _ in range(rows)]

In Java and Go, new int[m][n] and make([][]int, m) with per-row allocation are safe. In JavaScript/TypeScript, use Array.from with a mapping function to avoid shared references.

Accessing Elements

Elements live at matrix[row][col]. Rows run top to bottom (index 0 is the top row), columns run left to right. Get dimensions as:

Rows: len(matrix) / matrix.length / len(matrix)
Columns: len(matrix[0]) / matrix[0].length / len(matrix[0])

Always guard against empty matrices before accessing matrix[0].

Row-Major vs. Column-Major Iteration

Row-major (outer loop over rows, inner over columns) is the natural order and is cache-friendly in most languages. Column-major (outer loop over columns) is useful when you need to process each column as a unit, such as finding column sums.

Boundary Checking

Before reading matrix[r][c], verify:

0 <= r < rows
0 <= c < cols

A direction array makes neighbor iteration clean:

dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dr, dc in dirs:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # safe to access matrix[nr][nc]

Transposition

Transposing swaps rows and columns: element at (i, j) moves to (j, i). For a square matrix this can be done in-place by swapping the upper triangle with the lower triangle. For a rectangular matrix, you must create a new n x m matrix.

Rotation

Rotating a square matrix 90 degrees clockwise is a two-step process:

Transpose the matrix (swap matrix[i][j] with matrix[j][i])
Reverse each row

Counter-clockwise 90 degrees: transpose, then reverse each column (or reverse each row first, then transpose).

Common Applications

Image processing: rotate, flip, crop pixels
Game boards: tic-tac-toe, chess, minesweeper
Grid search: prep for BFS/DFS on 2D grids (islands, shortest path)
Spreadsheet operations: row/column sums, transposing data tables
Matrix math: addition, scalar multiplication (entry-wise operations)

Common Mistakes

Shared row references: In Python, [[0]*n]*m creates m references to the same list. Always use a list comprehension with for _ in range(m)
Swapping row and column indices: matrix[row][col] not matrix[col][row]. Rows = len(matrix), Cols = len(matrix[0])
Forgetting empty matrix check: Accessing matrix[0] on an empty matrix throws an error. Always check len(matrix) > 0 and len(matrix[0]) > 0 first
Off-by-one in boundary checks: Valid indices are 0 to rows - 1 and 0 to cols - 1. Using <= instead of < causes index-out-of-bounds
Assuming square matrix: Many matrices have rows != cols. Always use separate row and column counts
Modifying during iteration: Changing cell values while iterating can corrupt later reads. Mark cells first, then apply changes in a second pass
In-place transpose on rectangular matrix: In-place swap only works for square matrices. Rectangular matrices need a new output matrix

When to Use

Create or initialize a 2D grid

Iterate over all cells in a matrix

Access neighbors (up, down, left, right) of a cell

Check if a coordinate is within bounds

Transpose rows and columns

Rotate a matrix 90 degrees

Process rows, columns, or diagonals independently

Flatten a 2D array to 1D or reshape 1D to 2D

Perform entry-wise operations (add, scale, compare two matrices)

Template

1# --- Row-Major Traversal ---
2def traverse(matrix):
3    """Visit every cell row by row"""
4    if not matrix or not matrix[0]:
5        return
6    m, n = len(matrix), len(matrix[0])
7    for r in range(m):
8        for c in range(n):
9            process(matrix[r][c])
10
11# --- Safe Neighbor Access ---
12def get_neighbors(matrix, r, c):
13    """Return valid 4-directional neighbors"""
14    m, n = len(matrix), len(matrix[0])
15    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
16    neighbors = []
17    for dr, dc in dirs:
18        nr, nc = r + dr, c + dc
19        if 0 <= nr < m and 0 <= nc < n:
20            neighbors.append(matrix[nr][nc])
21    return neighbors
22
23# --- Transpose ---
24def transpose(matrix):
25    """Swap rows and columns (works for any shape)"""
26    if not matrix:
27        return []
28    m, n = len(matrix), len(matrix[0])
29    return [[matrix[r][c] for r in range(m)] for c in range(n)]
30
31# --- Rotate 90 Clockwise (square, in-place) ---
32def rotate_clockwise(matrix):
33    n = len(matrix)
34    # Transpose
35    for i in range(n):
36        for j in range(i + 1, n):
37            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
38    # Reverse each row
39    for row in matrix:
40        row.reverse()

{ }

Syntax Reference

1# === Creation ===
2rows, cols = 3, 4
3matrix = [[0] * cols for _ in range(rows)]     # 3x4 zeros
4matrix = [[1, 2], [3, 4], [5, 6]]              # literal
5
6# === Dimensions ===
7m = len(matrix)          # number of rows
8n = len(matrix[0])       # number of columns
9
10# === Access ===
11val = matrix[r][c]       # get element at row r, col c
12matrix[r][c] = val       # set element
13
14# === Row Iteration ===
15for r in range(m):
16    for c in range(n):
17        process(matrix[r][c])
18
19# === Column Iteration ===
20for c in range(n):
21    for r in range(m):
22        process(matrix[r][c])
23
24# === Boundary Check ===
25def in_bounds(r, c, m, n):
26    return 0 <= r < m and 0 <= c < n
27
28# === 4-Directional Neighbors ===
29dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
30for dr, dc in dirs:
31    nr, nc = r + dr, c + dc
32    if 0 <= nr < m and 0 <= nc < n:
33        process(matrix[nr][nc])
34
35# === Get Row / Column ===
36row = matrix[r]                        # entire row
37col = [matrix[r][c] for r in range(m)] # entire column
38
39# === Flatten ===
40flat = [val for row in matrix for val in row]

📋

Common Recipes

1# --- Transpose (any shape) ---
2def transpose(matrix):
3    if not matrix:
4        return []
5    m, n = len(matrix), len(matrix[0])
6    return [[matrix[r][c] for r in range(m)] for c in range(n)]
7
8# --- Rotate 90 Degrees Clockwise (square, in-place) ---
9def rotate_clockwise(matrix):
10    n = len(matrix)
11    # Step 1: Transpose
12    for i in range(n):
13        for j in range(i + 1, n):
14            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
15    # Step 2: Reverse each row
16    for row in matrix:
17        row.reverse()
18
19# --- Get Column as List ---
20def get_column(matrix, c):
21    return [matrix[r][c] for r in range(len(matrix))]
22
23# --- Matrix Addition ---
24def add_matrices(a, b):
25    m, n = len(a), len(a[0])
26    return [[a[r][c] + b[r][c] for c in range(n)] for r in range(m)]
27
28# --- Flatten 2D to 1D ---
29def flatten(matrix):
30    return [val for row in matrix for val in row]
31
32# --- Reshape 1D to 2D ---
33def reshape(flat, rows, cols):
34    return [flat[r * cols:(r + 1) * cols] for r in range(rows)]
35
36# --- Row and Column Sums ---
37def row_sums(matrix):
38    return [sum(row) for row in matrix]
39
40def col_sums(matrix):
41    m, n = len(matrix), len(matrix[0])
42    return [sum(matrix[r][c] for r in range(m)) for c in range(n)]

O(n)

Complexity

Operation	Time	Notes
Access element	O(1)	Direct index into row then column
Full traversal	O(m x n)	Visit every cell once
Get row	O(n)	Copy n elements
Get column	O(m)	One element per row
Transpose	O(m x n)	O(1) extra if square, O(m x n) if rectangular
Rotate 90 (square)	O(n^2)	Transpose + reverse rows, in-place
Matrix addition	O(m x n)	Entry-wise operation
Flatten to 1D	O(m x n)	Copy all elements
Boundary check	O(1)	Compare row/col against limits

Watch Out

✗Shared row references: In Python, `[[0]*n]*m` creates m references to the same list. Always use a list comprehension with `for _ in range(m)`
✗Swapping row and column indices: `matrix[row][col]` not `matrix[col][row]`. Rows = `len(matrix)`, Cols = `len(matrix[0])`
✗Forgetting empty matrix check: Accessing `matrix[0]` on an empty matrix throws an error. Always check `len(matrix) > 0` and `len(matrix[0]) > 0` first
✗Off-by-one in boundary checks: Valid indices are `0` to `rows - 1` and `0` to `cols - 1`. Using `<=` instead of `<` causes index-out-of-bounds
✗Assuming square matrix: Many matrices have `rows != cols`. Always use separate row and column counts
✗Modifying during iteration: Changing cell values while iterating can corrupt later reads. Mark cells first, then apply changes in a second pass
✗In-place transpose on rectangular matrix: In-place swap only works for square matrices. Rectangular matrices need a new output matrix

PRACTICE PROBLEMS

Sorting & Comparators

Bit Manipulation Basics