Introduction to Matrix

A matrix is a two-dimensional array laid out in contiguous memory so that the address of element A[i][j] is computed directly from i and j via arithmetic — base + (i * n + j) * elemSize for an m×n row-major matrix — which is why access needs no traversal, unlike a linked structure.

Recognize the pattern

• Input is described as a grid, board, image, or 2D map of cells (explicit rows/cols).
• You must move between neighboring cells (4- or 8-directional) — flood fill, number of islands, shortest path on a grid.
• Sub-problems index naturally by two coordinates — DP tables like dp[i][j], edit distance, unique paths.
• You need O(1) lookup of "is there an edge between i and j" — adjacency matrix for dense graphs.

Brute force to optimal

Naive layout: simulate a 2D structure with a hash map keyed by (i,j) pairs. It works for sparse data but every access pays hashing cost, and neighboring cells can be scattered anywhere in the heap — no cache locality.

Matrix (array-of-arrays or a flattened 1D array): fixed-size contiguous storage. Access is direct address arithmetic; scanning a row touches consecutive memory, exploiting the CPU cache line and prefetcher. The trade-off is that resizing means reallocating and copying the whole block, and space is reserved for every cell whether used or not — wasteful for sparse data (e.g. a graph with few edges).

Complexity, derived

The column-scan cost is the key derivation people miss: in row-major storage, element A[i][j] and A[i+1][j] are n slots apart in memory, so a column walk jumps n elements each step — it can defeat the cache even though, per element touched, both scans do the same O(1) work — and for a square matrix (m = n) the two scans' totals, O(m) and O(n), are literally identical in Big-O while their real speed differs by the cache behavior.

Worked example: address computation and traversal order

Take the 3×3 matrix A = [[1,2,3],[4,5,6],[7,8,9]] stored row-major starting at base address 1000 with 4-byte ints.

A row-major traversal visiting i outer, j inner reads addresses 1000,1004,1008,...,1032 in strictly increasing order — one cache line typically covers several consecutive elements. Swapping the loop order (j outer, i inner) reads 1000,1012,1024,1004,1016,1028,... — a stride-12 pattern that can trigger a cache miss on every access for large matrices.

Java and Go: allocation and safe traversal

Both traversals below deliberately re-read each row's own length inside the loop rather than hoisting one fixed n before the loop — the discipline the Pitfalls section calls for, and the only version that stays correct if a row is ever ragged.

// Java — ragged-safe traversal
int[][] A = {{1,2,3},{4,5,6},{7,8,9}};
int m = A.length;
int sum = 0;
for (int i = 0; i < m; i++) {
    int n = A[i].length;        // per-row length, not a fixed outer n
    for (int j = 0; j < n; j++) {
        sum += A[i][j];
    }
}
// sum = 45 for the matrix above; still correct if a row is shorter/longer

// Go — slice of slices, same per-row-length discipline
A := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
sum := 0
for i := range A {
    for j := range A[i] {   // len(A[i]) per row, ragged-safe
        sum += A[i][j]
    }
}
// sum == 45; Go slices are ragged by default, so this is the natural idiom

Pitfalls

• Ragged arrays: in Java/C#/JS, rows of a 2D array can have different lengths (int[][] is really an array of array references) — always read A[i].length per row instead of assuming a fixed n, as the traversal above does.
• Swapped index order: confusing A[row][col] with A[x][y] (x=column) is a classic off-by-axis bug in grid/graph problems.
• Column-major traversal cost: looping column-outer over a large row-major matrix silently degrades performance from cache-friendly to cache-thrashing while the asymptotic complexity looks unchanged.
• Dense matrix for sparse data: using an adjacency matrix for a graph with n=10^5 nodes and few edges wastes O(n²) memory; an adjacency list is the correct alternative.

When to use / when not, and trade-offs

Use a matrix when the domain is naturally dense and grid-shaped (images, boards, DP tables, dense graphs) and you need O(1) random access plus cache-friendly bulk scans. Use it for adjacency representation only when the graph is dense (edges close to n²) or you need O(1) edge-existence checks.

Alternative — adjacency list / hash map of coordinates: better when data is sparse — space is O(number of actual entries) instead of O(m·n), and iterating only real neighbors avoids wasted work, at the cost of O(1) amortized (not guaranteed contiguous) access and worse cache locality per lookup.

Takeaways

• A matrix trades flexibility for O(1) address-computed access and cache-friendly contiguous scans.
• Row-major vs column-major layout matters for performance, not just correctness — walk with the grain.
• Dense, grid-shaped, coordinate-indexed problems are the tell; sparse relational data should prefer adjacency lists or maps.

Recall: Why can a column scan and a row scan on a square (m = n) row-major matrix both be O(n) yet perform very differently in practice?

Compiled from standard DSA references on array/matrix memory layout and cache behavior (CLRS-style algorithm analysis; common systems-programming treatments of row-major vs column-major storage).