Grids & Matrices

Grids & Matrices problems usually involve traversing a 2D board and maintaining visited state.

KEY TAKEAWAYS

• Directions Array: Use an array of offsets (e.g., [[0, 1], [1, 0], ...]) to simplify navigating neighbors in a grid.
• Boundary Checks: Always validate indices before accessing grid cells. A helper function like is_valid(r, c) keeps code clean.
• Matrix Traversal: Be comfortable iterating through grids in various orders: row-by-row, column-by-column, backwards, or in spirals.
• 2D Prefix Sums: For subgrid sum queries, use the inclusion-exclusion principle (add sides, subtract overlap).
• Matrix Transformations: Transposing swaps rows and columns ([r][c] -> [c][r]). Rotating involves mapping [r][c] to transformed coordinates (e.g., [c][n-1-r]).