Back to Study Material Data Structures and Algorithms

Matrix

A matrix is a two-dimensional array organized as rows and columns. In code, a matrix of m rows and n columns is typically represented as an array of m arra...

Matrix

Working with Two-Dimensional Arrays and Grid Algorithms

A matrix is a two-dimensional array organized as rows and columns. In code, a matrix of m rows and n columns is typically represented as an array of m arrays, each of length n. Accessing element at row i and column j is written as M[i][j] and costs O(1) because both index calculations are simple arithmetic.

Matrices model a wide range of real-world problems: pixel grids in image processing, adjacency matrices in graph algorithms, game boards, spreadsheet data, and coefficient matrices in linear algebra. Choosing the right traversal order and algorithm can mean the difference between an efficient solution and one that times out.

Traversal patterns are fundamental. Row-major traversal visits all elements of row 0, then row 1, and so on. This matches how most languages store matrices in memory (row-by-row), making it cache-friendly. Column-major traversal visits all elements of column 0, then column 1. In a row-major storage layout, each step in column traversal jumps by n elements in memory, causing frequent cache misses and running significantly slower on large matrices even though the asymptotic complexity is the same O(m times n).

Common matrix operations: transpose swaps M[i][j] with M[j][i] for all i and j. For an n by n matrix this takes O(n^2) time. Rotating a matrix ninety degrees clockwise can be done in-place for square matrices by first transposing, then reversing each row. Matrix multiplication of an m by k matrix with a k by n matrix produces an m by n result and takes O(m times k times n) with the naive algorithm.

Many interview problems involve grid traversal using depth-first or breadth-first search. Number of islands counts connected groups of land cells in a binary grid. Each BFS or DFS from an unvisited land cell marks an entire island in O(cells in island) time. Total time across all islands is O(m times n) since each cell is visited at most once.

Spiral traversal of a matrix is another common problem. Maintain four boundaries: top, bottom, left, right. Traverse the top row left to right, increment top. Traverse the right column top to bottom, decrement right. Traverse the bottom row right to left if top still is less than or equal to bottom, decrement bottom. Traverse the left column bottom to top, increment left. Repeat until boundaries cross.

Worked example: rotate a matrix 90 degrees clockwise in-place. Step 1: transpose (swap M[i][j] with M[j][i]). Step 2: reverse each row. Both steps are O(n^2) time and O(1) auxiliary space.

Interview tip: for matrix problems, always write out the index arithmetic on paper first. Off-by-one errors in boundary conditions for spiral traversal or rotation are the most common source of bugs.