2D Arrays & Matrices
Overview
A 2D array (or matrix) is an array of arrays. It organizes data into rows and columns, accessed via two indices, typically `matrix[row][col]`. Under the hood, memory is fundamentally 1-dimensional, so the computer flattens the grid into a single contiguous line.
Many real-world problems are inherently two-dimensional: maps, spreadsheets, images, and mathematical matrices. 2D arrays provide a natural mental model to represent and traverse these spatial structures.
Where used: Dynamic Programming: building a 2D table to cache subproblem results, Graph representations: Adjacency matrices represent connections between nodes
Why learn this
- Matrix traversal problems (like 'Spiral Matrix' or 'Number of Islands') are their own entire category of interview questions.
- Understanding how 2D arrays map to 1D memory is critical for writing cache-efficient code in performance-sensitive applications like graphics rendering.
- It introduces coordinate-based logic (moving up, down, left, right by manipulating row/col variables) which is essential for graph traversal.
Aha moment
# Python pitfall:
bad_grid = [[0] * 3] * 3
bad_grid[0][0] = 9
print(bad_grid)
# Output: [[9, 0, 0], [9, 0, 0], [9, 0, 0]]
# Correct way:
good_grid = [[0 for _ in range(3)] for _ in range(3)]
good_grid[0][0] = 9
print(good_grid)
# Output: [[9, 0, 0], [0, 0, 0], [0, 0, 0]]Prediction: Modifying `bad_grid[0][0]` will only change the top-left corner.
Common guess: Both grids behave exactly the same way.
The `* 3` operator duplicates REFERENCES to the same inner list. You don't have a 3x3 grid; you have one row with 3 pointers pointing to it. The list comprehension creates 3 distinct, independent lists in memory.
Common mistakes
- Confusing (x, y) with (row, col): In Cartesian math, (x, y) means (horizontal, vertical). But in 2D arrays, `matrix[r][c]` means `r` is the row (vertical position, Y-axis) and `c` is the column (horizontal position, X-axis). They are flipped.
- Out of bounds on non-square matrices: If a matrix is M x N, the row limit is M and the col limit is N. Assuming the matrix is square and using `matrix.length` for both bounds will crash on rectangular matrices.
- Shallow copying nested arrays: In Python, `[[0]*3]*3` creates a list containing three references to the EXACT SAME row. Modifying one row modifies all of them. You must use list comprehensions or loops to create independent rows.
Glossary
- contiguous line
- A continuous, unbroken sequence of memory.
- cache-efficient
- Written in a way that helps the computer memory.
- Cartesian math
- A coordinate system.
Recall questions
- How do you access the element in the 3rd row and 2nd column of a 0-indexed matrix?
- If you are at `matrix[r][c]`, what are the coordinates of the element directly above you?
- Why is iterating row-by-row (row-major order) faster than iterating column-by-column in memory?
Understanding checks
A matrix has 5 rows and 4 columns. To flatten it to a 1D array using row-major order, the formula for a 1D index is `(row * NUMBER_OF_COLUMNS) + col`. Why do we multiply by the number of columns instead of the number of rows?
Because to get to row 3, you have to skip entirely over row 0, row 1, and row 2. Each of those rows contains exactly `NUMBER_OF_COLUMNS` elements.
This is the fundamental math the compiler uses to translate a 2D access into a 1D memory address. Understanding it demystifies how multi-dimensional data is actually stored.
You write a function to search a grid. It checks `grid[r+1][c]` to look down. However, when you are on the very bottom row, the program crashes with an 'Index Out of Bounds' error. How do you fix this structurally?
You must check boundaries before accessing the index: `if r + 1 < len(grid): check(grid[r+1][c])`. Guarding directional moves is mandatory in grid traversal.
Boundary checking is the single most common source of bugs in matrix problems. You must always ensure the next coordinate is within `0 <= r < ROWS` and `0 <= c < COLS`.
Practice tasks
Define directional vectors
When traversing a matrix (like in a maze), it's messy to write 4 separate if-statements for Up, Down, Left, Right. Define an array of coordinate pairs `directions` that you can loop over to safely get the 4 adjacent neighbors of `(r, c)`.
Continue learning
Previous: Arrays & Memory