Matrix & 2D Arrays · Data Structures & Algorithms

Grids show up everywhere — images, boards, maps. Most matrix questions are a careful traversal or a graph search in disguise.

A 2D array (matrix) stores elements in rows and columns; matrix[i][j] is reached in O(1). Visiting every cell is O(m×n). The recurring skills are ordered traversal (row-major, spiral, diagonal), in-place transforms (transpose, rotate), and treating the grid as a graph (islands, mazes).

A grid is often a graph

Many 'grid' problems — number of islands, shortest path in a maze, flood fill — are really BFS or DFS where each cell is a node connected to its four neighbours. Recognising that turns a scary 2D problem into a familiar traversal.

Search a row- and column-sorted matrix in O(m+n)

r = 0;  c = cols - 1            // start at the top-right
while r < rows and c >= 0:
    if M[r][c] == target: return (r, c)
    if M[r][c] > target: c = c - 1   // too big -> go left
    else: r = r + 1                 // too small -> go down
return not found

O(m + n)→O(1)

From the corner, each step eliminates a whole row or column.

⚡ The edge

In a matrix sorted along rows and columns, start at the top-right corner: if the value is too big move left, too small move down — O(m+n), not O(m×n).
If a problem mentions connected cells, regions, or shortest path on a grid, reach for BFS/DFS flood fill — it is the same traversal you already know.

Worked example

How do you rotate an n×n image 90° clockwise in place?

First transpose the matrix — swap M[i][j] with M[j][i] — turning rows into columns.
Then reverse each row.
Transpose + reverse-rows equals a 90° clockwise rotation, all in O(n²) time and O(1) extra space.

Answer: Transpose, then reverse each row (in place)

Worked example

Count the islands (groups of connected 1s) in a grid of 0s and 1s.

Scan every cell; when you hit a 1 not yet visited, start a flood fill (DFS/BFS) from it.
The flood fill marks the whole connected region of 1s as visited.
Each new flood fill you launch is one island; count the launches.

Answer: Run DFS/BFS from each unvisited land cell; the launch count is the answer — O(m×n)

⚠ Watch out

Always bounds-check before accessing a neighbour: 0 ≤ r < rows and 0 ≤ c < cols.
Rotating in place is error-prone — the transpose-then-reverse trick avoids index gymnastics.
Mark cells visited (or mutate them) during flood fill, or you will loop forever.