Matrix

Matrix / 2D Grid

Back to Index

A 2D array. Most matrix problems are graph problems in disguise — cells are nodes, adjacency is up/down/left/right.

Properties

• Access: O(1) by grid[r][c]
• n×m grid has n*m cells
• 4-directional movement is most common; 8-directional for diagonal problems

Direction Vectors

DIRS4 = [(0,1),(0,-1),(1,0),(-1,0)]           # up/down/left/right
DIRS8 = [(0,1),(0,-1),(1,0),(-1,0),
         (1,1),(1,-1),(-1,1),(-1,-1)]          # includes diagonals
 
# Bounds check helper
def in_bounds(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

Common Techniques

DFS / BFS on Grid (DFS, BFS)

def dfs(r, c):
    if not in_bounds(r, c, rows, cols) or visited[r][c] or grid[r][c] != target:
        return
    visited[r][c] = True
    for dr, dc in DIRS4:
        dfs(r + dr, c + dc)

In-place Visited Marking

Modify the grid itself to mark visited cells (restore afterward if needed).

grid[r][c] = '#'   # mark
# ... recurse ...
grid[r][c] = original  # restore (if backtracking)

Diagonal Traversal

• Main diagonal (top-left to bottom-right): r - c is constant
• Anti-diagonal (top-right to bottom-left): r + c is constant

Patterns That Use This

BFS — shortest path, multi-source spreading DFS — island counting, flood fill, connected components Dynamic Programming — path problems, counting paths Backtracking — word search, constraint satisfaction

---

Problems Using This Data Structure