Last modified: September 14, 2025
This article is written in: πΊπΈ
Matrices represent images, game boards, and maps. Many classic problems reduce to transforming matrices, traversing them, or treating grids as graphs for search.
Rows indexed $0..R-1$, columns $0..C-1$; cell $(r,c)$.
Rows increase down, columns increase right. Think βtop-left is $(0,0)$β, not a Cartesian origin.
Visual index map (example $R=6$, $C=8$; each cell labeled $rc$):
c β 0 1 2 3 4 5 6 7
r β +----+----+----+----+----+----+----+----+
0 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
+----+----+----+----+----+----+----+----+
1 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
+----+----+----+----+----+----+----+----+
2 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
+----+----+----+----+----+----+----+----+
3 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
+----+----+----+----+----+----+----+----+
4 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
+----+----+----+----+----+----+----+----+
5 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
+----+----+----+----+----+----+----+----+
Handy conversions (for linearization / array-of-arrays):
Row-major vs column-major arrows (same $3\times 6$ grid):
Row-major (r, then c): Column-major (c, then r):
β β β β β β β β β
β β β β
β β β β β β β β β
β β β β
β β β β β β β β β
Neighborhoods: $\mathbf{4}$-dir $\Delta={(-1,0),(1,0),(0,-1),(0,1)}$; $\mathbf{8}$-dir adds diagonals.
The offsets $(\Delta r,\Delta c)$ are applied as $(r+\Delta r,\ c+\Delta c)$.
4-neighborhood (β+β):
#
(r-1,c)
β
(r,c-1) β (r,c) β (r,c+1)
β
(r+1,c)
8-neighborhood (βΓβ adds diagonals):
(r-1,c-1) (r-1,c) (r-1,c+1)
\ β /
\ β /
(r,c-1) ββββ (r,c) ββββ (r,c+1)
/ β \
/ β \
(r+1,c-1) (r+1,c) (r+1,c+1)
Typical direction arrays (keep them consistent to avoid bugs):
// 4-dir
dr = [-1, 1, 0, 0]
dc = [ 0, 0, -1, 1]
// 8-dir
dr8 = [-1,-1,-1, 0, 0, 1, 1, 1]
dc8 = [-1, 0, 1,-1, 1,-1, 0, 1]
Boundary checks (always guard neighbors):
0 β€ nr < R and 0 β€ nc < C
Edge/inside intuition:
out of bounds
βββββββββββββββββββ
β Β· Β· Β· Β· Β· Β· Β· Β· β
β Β· +---+---+---+ β
β Β· | a | b | c | β β valid cells
β Β· +---+---+---+ β
β Β· | d | e | f | β
β Β· +---+---+---+ β
β Β· Β· Β· Β· Β· Β· Β· Β· β
βββββββββββββββββββ
Swap across the main diagonal: $A_{r,c} \leftrightarrow A_{c,r}$ (square). For non-square, result shape is $C\times R$.
Example inputs and outputs
Example 1 (square)
$$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad\Rightarrow\quad A^{\mathsf{T}} = \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} $$
Mathematical formula (3Γ3)
$$ (A^T){r,c}=A{c,r},\quad 0\le r,c<3 $$
Pseudocode (square, in-place)
n = 3 # for this example; generalize to n = size
for r in 0..n-1:
for c in r+1..n-1:
swap A[r][c], A[c][r]
Example 2 (rectangular)
$$ \text{Input: } \quad A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \ (2 \times 3) $$
$$ \text{Output: } \quad A^{\mathsf{T}} = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \ (3 \times 2) $$
Mathematical formula (2Γ3 β 3Γ2)
$$ (A^{\mathsf T}){r,c}=A{c,r},\quad 0\le r<3,\ 0\le c<2 $$
Pseudocode (rectangular, new matrix)
R, C = 2, 3
B = zeros(C, R)
for r in 0..R-1:
for c in 0..C-1:
B[c][r] = A[r][c]
How it works
Iterate pairs once and swap. For square matrices, can be in-place by visiting only $c>r$.
Reverse each row left $\leftrightarrow$ right.
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 3 & 2 & 1 \\ 6 & 5 & 4 \end{bmatrix} $$
Mathematical formula (2Γ3)
$$ B_{r,c}=A_{r,\ C-1-c},\quad 0\le r<2,\ 0\le c<3 $$
Pseudocode (in-place)
R, C = 2, 3
for r in 0..R-1:
for c in 0..(C//2 - 1):
swap A[r][c], A[r][C-1-c]
Reverse each column top $\leftrightarrow$ bottom.
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 7 & 8 & 9 \\ 4 & 5 & 6 \\ 1 & 2 & 3 \end{bmatrix} $$
Mathematical formula (3Γ3)
$$ B_{r,c}=A_{R-1-r,\ c},\quad 0\le r,c<3 $$
Pseudocode (in-place)
R, C = 3, 3
for r in 0..(R//2 - 1):
for c in 0..C-1:
swap A[r][c], A[R-1-r][c]
Use transpose + reversals for square in-place rotations; rectangular rotations produce new shape $(R\times C)\to(C\times R)$.
Transpose, then reverse each row.
Example inputs and outputs
Example 1 (3Γ3)
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \end{bmatrix} $$
Mathematical formula (nΓn)
$$ B_{r,c}=A_{n-1-c,\ r},\quad 0\le r,c<n $$
Pseudocode (square, in-place via basics)
n = 3
# transpose
for r in 0..n-1:
for c in r+1..n-1:
swap A[r][c], A[c][r]
# reverse each row
for r in 0..n-1:
for c in 0..(n//2 - 1):
swap A[r][c], A[r][n-1-c]
Example 2 (2Γ3 β 3Γ2)
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 4 & 1 \\ 5 & 2 \\ 6 & 3 \end{bmatrix} $$
Mathematical formula (RΓC β CΓR)
$$ B_{r,c}=A_{R-1-c,\ r},\quad 0\le r<C,\ 0\le c<R\ \ (R{=}2,\ C{=}3) $$
Pseudocode (rectangular, direct mapping)
R, C = 2, 3
B = zeros(C, R)
for r in 0..C-1: # rows of B
for c in 0..R-1: # cols of B
B[r][c] = A[R-1-c][r]
How it works
Transpose swaps axes; reversing each row aligns columns to rows of the rotated image.
Transpose, then reverse each column (or reverse rows, then transpose).
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 3 & 6 & 9 \\ 2 & 5 & 8 \\ 1 & 4 & 7 \end{bmatrix} $$
Mathematical formula (nΓn)
$$ B_{r,c}=A_{c,\ n-1-r},\quad 0\le r,c<n $$
Pseudocode (square, via basics)
n = 3
# transpose
for r in 0..n-1:
for c in r+1..n-1:
swap A[r][c], A[c][r]
# reverse each column (vertical flip)
for r in 0..(n//2 - 1):
for c in 0..n-1:
swap A[r][c], A[n-1-r][c]
Pseudocode (general, direct mapping)
# A is R x C, B is C x R
B = zeros(C, R)
for r in 0..C-1:
for c in 0..R-1:
B[r][c] = A[c][C-1-r]
How it works
Transpose, then flip vertically to complete the counterclockwise rotation.
Equivalent to reversing rows, then reversing columns (or two 90Β° rotations).
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } \begin{bmatrix} 9 & 8 & 7 \\ 6 & 5 & 4 \\ 3 & 2 & 1 \end{bmatrix} $$
Mathematical formula (RΓC β RΓC)
$$ B_{r,c}=A_{R-1-r,\ C-1-c},\quad 0\le r<R,\ 0\le c<C $$
Pseudocode (in-place via two flips)
R, C = 3, 3 # generalize as needed
# reverse rows
for r in 0..R-1:
for c in 0..(C//2 - 1):
swap A[r][c], A[r][C-1-c]
# reverse columns
for r in 0..(R//2 - 1):
for c in 0..C-1:
swap A[r][c], A[R-1-r][c]
Pseudocode (direct mapping to new matrix)
B = zeros(R, C)
for r in 0..R-1:
for c in 0..C-1:
B[r][c] = A[R-1-r][C-1-c]
How it works
Horizontal + vertical flips relocate each element to $(R-1-r,\ C-1-c)$.
270Β° CW = 90Β° CCW; 270Β° CCW = 90Β° CW. Reuse the 90Β° procedures.
Mathematical formulas (general)
270Β° CW (i.e., 90Β° CCW):
$$ B_{r,c}=A_{c,\ C-1-r},\quad B\in\mathbb{R}^{C\times R}. $$
270Β° CCW (i.e., 90Β° CW):
$$ B_{r,c}=A_{R-1-c,\ r},\quad B\in\mathbb{R}^{C\times R}. $$
Pseudocode (via composition, square in-place)
# 270Β° CW == 90Β° CCW
transpose(A)
reverse_columns_in_place(A)
# 270Β° CCW == 90Β° CW
transpose(A)
reverse_rows_in_place(A)
Rotate each ring by cycling 4 positions.
How it works
For layer $\ell$ with bounds $ [\ell..n-1-\ell]$, for each offset move:
top β left, left β bottom, bottom β right, right β top
Mathematical mapping (per moved element)
For an $n\times n$ matrix and a position $(r,c)$ on layer $\ell$, a 90Β° CW rotation sends
$$ (r,c)\ \mapsto\ (c,\ n-1-r)\ \mapsto\ (n-1-r,\ n-1-c)\ \mapsto\ (n-1-c,\ r) $$
Pseudocode (explicit loops, in-place)
n = size(A)
for layer in 0..(n//2 - 1):
first = layer
last = n - 1 - layer
for i in first..last-1:
offset = i - first
# save top
tmp = A[first][i]
# left -> top
A[first][i] = A[last - offset][first]
# bottom -> left
A[last - offset][first] = A[last][last - offset]
# right -> bottom
A[last][last - offset] = A[i][last]
# top (saved) -> right
A[i][last] = tmp
Read outer layer, then shrink bounds.
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{bmatrix} $$
$$ \text{Output sequence: } 1,2,3,4,8,12,11,10,9,5,6,7 $$
Mathematical formulation (general $R\times C$)
Let the matrix indices be $(r,c)$ with $0\le r<R,\ 0\le c<C$. For layer $\ell=0,1,\dots,L-1$ where $L=\left\lceil \tfrac{\min(R,C)}{2}\right\rceil$, set
$$ t=\ell,\quad b=R-1-\ell,\quad left=\ell,\quad rgt=C-1-\ell $$
Visit, in order:
Concatenate these per layer until all elements are visited.
Pseudocode (loops)
R, C = dims(A)
top, bottom = 0, R - 1
left, right = 0, C - 1
out = []
while top <= bottom and left <= right:
# top row
for c in left..right:
out.append(A[top][c])
top += 1
# right column
for r in top..bottom:
out.append(A[r][right])
right -= 1
# bottom row (if any)
if top <= bottom:
for c in right..left step -1:
out.append(A[bottom][c])
bottom -= 1
# left column (if any)
if left <= right:
for r in bottom..top step -1:
out.append(A[r][left])
left += 1
How it works
Maintain top, bottom, left, right. Walk edges in order; after each edge, move the corresponding bound inward.
Visit cells grouped by $s=r+c$; alternate direction per diagonal to keep locality if desired.
Example inputs and outputs
Example
$$ \text{Input: } \begin{bmatrix} a & b & c \\ d & e & f \end{bmatrix} \quad\Rightarrow\quad \text{One order: } a, b, d, e, c, f $$
Mathematical formulation (general $R\times C$)
Let $s=r+c$. For $s=0,1,\dots,R+C-2$, define
$$ r_{\min}(s)=\max!\big(0,\ s-(C-1)\big) $$
$$ r_{\max}(s)=\min!\big(R-1,\ s\big) $$
The diagonal set is ${(r,s-r)\mid r_{\min}(s)\le r\le r_{\max}(s)}$.
Traverse with alternating direction:
$$ \begin{cases} \text{if } s \text{ even: } r=r_{\max}(s), r_{\max}(s)-1,\dots,r_{\min}(s);\[2pt] \text{if } s \text{ odd: } r=r_{\min}(s), r_{\min}(s)+1,\dots,r_{\max}(s). \end{cases} $$
(This parity choice reproduces the example order $a,b,d,e,c,f$ for $R=2,C=3$.)
Pseudocode (loops, alternating direction)
R, C = dims(A)
out = []
for s in 0..(R + C - 2):
r_lo = max(0, s - (C - 1))
r_hi = min(R - 1, s)
if s % 2 == 0:
# even s: go downward-left (decreasing r)
for r in r_hi..r_lo step -1:
c = s - r
out.append(A[r][c])
else:
# odd s: go upward-right (increasing r)
for r in r_lo..r_hi:
c = s - r
out.append(A[r][c])
Each cell is a node; edges connect neighboring walkable cells.
Grid-as-graph view (4-dir edges). Each cell is a node; edges connect neighbors that are βpassableβ. Great for BFS shortest paths on unweighted grids.
Example map (walls #
, free .
, start S
, target T
).
Left: the map. Right: BFS distances (4-dir) from S
until T
is reached.
Original Map:
#####################
#S..#....#....#.....#
#.#.#.##.#.##.#.##..#
#.#...#..#.......#.T#
#...###.....###.....#
#####################
BFS layers (distance mod 10):
#####################
#012#8901#9012#45678#
#1#3#7##2#8##1#3##89#
#2#456#43#7890123#7X#
#345###54567###34567#
#####################
Legend: walls (#), goal reached (X)
BFS explores in expanding βringsβ; with 4-dir edges, each step increases Manhattan distance by 1 (unless blocked). Time $O(RC)$, space $O(RC)$ with a visited matrix/queue.
Obstacles / costs / diagonals.
#
(or where cost is $\infty$).Common symbols:
. = free cell # = wall/obstacle
S = start T = target/goal
V = visited * = on current path / frontier
Find the minimum steps from S to T.
Example inputs and outputs
Example
$$ \text{Grid (0 = open, 1 = wall), } S = (0,0), T = (2,3) $$
$$ \begin{bmatrix} S & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & T \end{bmatrix} \quad\Rightarrow\quad \text{Output: distance } = 5 $$
How it works
Push S to a queue, expand in 4-dir layers, track distance/visited; stop when T is dequeued.
Count regions of β1βs via DFS/BFS.
Example inputs and outputs
$$ \text{Input: } \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad\Rightarrow\quad \text{Output: } 2 \ \text{islands} $$
How it works
Scan cells; when an unvisited β1β is found, flood it (DFS/BFS) to mark the whole island.
Find a word by moving to adjacent cells (4-dir), using each cell once per path.
Example inputs and outputs
$$ \text{Board: } \begin{bmatrix} A & B & C & E \\ S & F & C & S \\ A & D & E & E \end{bmatrix}, \quad \text{Word: } "ABCCED" \quad\Rightarrow\quad \text{Output: true} $$
Mathematical formulation (general)
Let the word be $W=W_0W_1\cdots W_{L-1}$ and the grid be $G\in\Sigma^{R\times C}$. We seek a path $P=\big((r_0,c_0),\ldots,(r_{L-1},c_{L-1})\big)$ such that
$$ \begin{aligned} &\text{(match)} && G_{r_i,c_i}=W_i,\quad i=0,\ldots,L-1;\\ &\text{(adjacent)} && |r_{i+1}-r_i|+|c_{i+1}-c_i|=1,\quad i=0,\ldots,L-2;\\ &\text{(no reuse)} && (r_i,c_i)\neq(r_j,c_j)\ \text{for all }i\ne j. \end{aligned} $$
Instantiation for the example (one valid path)
$$ P=\big((0,0),(0,1),(0,2),(1,2),(2,2),(2,1)\big) $$
gives $A\to B\to C\to C\to E\to D = \text{"ABCCED"}$.
Pseudocode (DFS with loops over starts and 4-neighbors)
R, C = dims(board)
L = len(word)
visited = array(R, C, fill=false)
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def dfs(r, c, i):
if r < 0 or r >= R or c < 0 or c >= C:
return false
if visited[r][c] or board[r][c] != word[i]:
return false
if i == L - 1:
return true
visited[r][c] = true
for k in 0..3:
nr = r + dr[k]
nc = c + dc[k]
if dfs(nr, nc, i + 1):
return true
visited[r][c] = false
return false
# try every starting cell
for r in 0..R-1:
for c in 0..C-1:
if dfs(r, c, 0):
return true
return false
How it works
From each starting match, DFS to next char; mark visited (temporarily), backtrack on failure.
Pruning: early letter mismatch; frequency precheck; prefix trie when searching many words.
Place words to slots with crossings; verify consistency at intersections.
Mathematical formulation
Let $S$ be the set of slots (across/down). Each slot $s\in S$ has a length $\ell(s)$ and ordered cell coordinates $\mathrm{cells}(s) = \big((r_0,c_0),\ldots,(r_{\ell(s)-1},c_{\ell(s)-1})\big)$. Let $D$ be the dictionary; define $D_\ell={w\in D:|w|=\ell}$. Known letters from the grid induce a pattern constraint $P_s\in(\Sigma\cup{_})^{\ell(s)}$.
Find an assignment $f:S\to D$ such that, for all $s\in S$,
$$ f(s)\in D_{\ell(s)}\quad\text{and}\quad \forall i\ (P_s[i]\neq _ \Rightarrow f(s)[i]=P_s[i]), $$
and for every intersection between slots $s$ at index $i$ and $t$ at index $j$,
$$ f(s)[i]=f(t)[j]. $$
(Optionally enforce all-different: $s\neq t \Rightarrow f(s)\neq f(t)$.)
Pseudocode (backtracking with loops, MRV + trie filtering)
# Preprocess
slots = extract_slots(grid) # with cells(s) and pattern P_s
trie = build_trie(dictionary) # for prefix/length checks
# Build initial domains from patterns and lengths
domains = dict()
for s in slots:
domains[s] = { w in dictionary | len(w) == len(s) and matches_pattern(w, P_s) }
# Order slots: Most-Restricted-Variable (smallest domain first)
slots.sort_by(|domains[s]| ascending, tiebreak by number_of_intersections)
used = set() # if words must be unique
assignment = dict()
def consistent(s, w):
# check crossings vs assigned neighbors
for each intersection (s,i) with (t,j):
if t in assignment and assignment[t][j] != w[i]:
return false
return true
def forward_check_update_domains(s, w, removed):
# reduce neighbor domains by letter constraints from placing w at s
for each intersection (s,i) with (t,j):
for each v in copy(domains[t]):
if v[j] != w[i]:
domains[t].remove(v); removed.append((t, v))
def undo_forward_check(removed):
for (t, v) in removed:
domains[t].add(v)
def backtrack(idx):
if idx == len(slots):
return true
s = slots[idx]
# iterate candidates; optionally skip ones already used
for w in iterate(domains[s]):
if w in used:
continue
if not consistent(s, w):
continue
assignment[s] = w
used.add(w)
removed = []
forward_check_update_domains(s, w, removed)
if backtrack(idx + 1):
return true
undo_forward_check(removed)
used.remove(w)
del assignment[s]
return false
# Start search
if backtrack(0):
return assignment # filled crossword
else:
return failure
How it works
Backtrack over slot assignments; use a trie for prefix feasibility; order by most constrained slot first.