2D Array / Matrices

Representation and Traversal

A matrix with M rows and N columns can be thought of as a grid. Accessing an element is done via two indices: matrix[row][col].

Traversal: A common task is to iterate through every element. This is typically done with nested loops. The standard way this is performed is in row-major order, where the algorithm processes all elements of the first row, then all elements of the second row, and so on. This matches how 2D arrays are often laid out in computer memory, which can have performance benefits due to caching.

# Python for traversing a matrix
rows = len(matrix)
cols = len(matrix[0])
for r in range(rows):
  for c in range(cols):
    # Do something with matrix[r][c]

Interactive Demo

Press play on the simulation below to see a row-major traversal in action. The highlighted cell shows the order in which elements are typically accessed by nested loops.

Common Matrix Problems & Techniques

1. Spiral Traversal:

Problem: Given an m x n matrix, return all elements of the matrix in spiral order.

Approach: Use four pointers to represent the boundaries of the current layer: top, bottom, left, and right. Traverse the top row from left to right, then the right column from top to bottom, then the bottom row from right to left, and finally the left column from bottom to top. After each traversal, shrink the boundaries inwards and repeat until the boundaries cross.

2. Rotate Image:

Problem: You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You have to do this in-place.

Approach: A clever two-step process can solve this. First, transpose the matrix (swap matrix[i][j] with matrix[j][i]). Then, reverse each row of the transposed matrix. This results in a 90-degree clockwise rotation.

3. Set Matrix Zeroes:

Problem: Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. Do this in-place.

Approach: A naive approach using extra O(m*n) space is easy. To do it in O(1) extra space (excluding the matrix itself), we can use the first row and first column of the matrix as markers. First, check if the original first row or first column contains any zeroes and store this information in boolean variables. Then, iterate through the rest of the matrix (from [1,1]). If matrix[i][j] is 0, set matrix[i][0] = 0 and matrix[0][j] = 0. After marking, iterate through the matrix again and set elements to zero based on the markers in the first row/column. Finally, use the initial boolean variables to handle the first row and column themselves.

4. Search in a 2D Sorted Matrix:

Problem: The matrix is sorted in two ways: integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of the previous row.

Approach: Treat the 2D matrix as a single sorted 1D array. You can use binary search directly. The challenge is mapping a 1D index mid back to 2D coordinates: row = mid / N, col = mid % N (where N is the number of columns).