2D arrays & matrix traversal

A 2D array (matrix or grid) has R rows and C columns, and cell (r, c) sits in row r, column c. In memory it is usually stored row by row (row-major order, used by C and NumPy by default), so cell (r, c) is at flat index r * C + c.

Grid problems fall into a few families: fixed-order walks (row by row, column by column, diagonals, spiral), geometric transforms (transpose, rotate), and treating the grid as a graph where each cell links to its 4 (or 8) neighbours, so BFS and DFS apply.

1. 1Dimensions: rows = len(grid), cols = len(grid[0]). Check for an empty grid first.
2. 2Neighbours: keep a direction list such as [(1, 0), (-1, 0), (0, 1), (0, -1)] and add each to (r, c). Always check 0 <= nr < rows and 0 <= nc < cols before reading.
3. 3Visited: mark cells when they are added to the queue or stack (not when popped), either in a set or by overwriting the cell if you are allowed to modify the input.
4. 4Diagonals: every cell on the same top-left to bottom-right diagonal has the same r - c; on the same anti-diagonal, the same r + c. Group by those values.
5. 5Rotate an n x n matrix 90 degrees clockwise in place: transpose (swap grid[i][j] with grid[j][i] for j > i), then reverse each row.
6. 6Spiral order: keep four boundaries (top, bottom, left, right), walk one edge, shrink that boundary, and stop when they cross.

from collections import deque


def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            islands += 1                      # new island found
            grid[r][c] = '0'                  # mark visited
            q = deque([(r, c)])
            while q:
                cr, cc = q.popleft()
                for dr, dc in dirs:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        q.append((nr, nc))
    return islands

Each unvisited land cell starts a new island, and a BFS erases every land cell connected to it so it is never counted again. Cells are marked when enqueued, so no cell enters the queue twice. Time O(R * C); extra space for the queue is O(R * C) in the worst case. The grid is modified in place; copy it first if the caller needs it intact.

Cost: Traversals and BFS/DFS over a grid: O(R * C) time. Visited set or queue: O(R * C) space worst case. In-place rotate and spiral: O(1) extra space besides output.