ReviseAlgo Logo

Arrays and Strings

Multidimensional Arrays

2D and 3D arrays for matrices and grids

Interview: Matrix problems are extremely common in interviews — 2D grid traversal, dynamic programming tables, image processing

Multidimensional Arrays

A multidimensional array in C++ is an array of arrays. A 2D array int m[3][4] is stored as 3 consecutive groups of 4 integers — a single flat block of 12 integers in row-major order. Understanding this layout is critical for writing cache-efficient matrix algorithms.

Row-Major Storage

C++ stores 2D arrays in row-major order: all elements of row 0 come first, then row 1, etc. This means iterating over columns in the inner loop (stepping through consecutive memory) is more cache-friendly than iterating rows in the inner loop (jumping across rows = cache striding). Always iterate in row order: outer loop over rows, inner loop over columns.

Passing to Functions

When passing a 2D C-array to a function, the first dimension decays to a pointer but all subsequent dimensions must be specified: void process(int arr[][4], int rows). This makes fixed-size 2D arrays inflexible for varying dimensions. Use std::vector<std::vector<T>> or a flat vector with manual indexing for runtime-sized matrices.

Dynamic 2D Arrays

For variable-size matrices, use vector<vector<int>> for simplicity or a flat vector<int> of size rows×cols with manual indexing arr[row * cols + col] for performance (single contiguous allocation, better cache behavior than vector-of-vectors which scatters rows in memory).

Interview Corner

Q: Why is iterating a 2D array with columns in the inner loop faster than rows?

A: C++ stores 2D arrays in row-major order — row elements are contiguous. Iterating for(i) for(j) arr[i][j] accesses sequential memory addresses — the CPU prefetcher loads upcoming elements into cache before they are needed. Iterating for(j) for(i) arr[i][j] strides across rows, each access jumping by the row size — causing frequent cache misses. For a 1000×1000 int matrix, row-major iteration can be 5–10× faster.

Q: When would you use a flat vector vs vector-of-vectors for a matrix?

A: Flat vector (vector<int> m(rows*cols)) is a single contiguous allocation — better cache locality, one allocation, and the memory layout matches hardware expectations. Vector-of-vectors allocates each row separately — scattered memory causes more cache misses. Use flat vector for performance-critical math; vector-of-vectors for jagged arrays or simpler interview code where each row has a different length.

Common Pitfalls

  • Column-major iteration on 2D arrays: Swapping the loop order (inner loop over rows) creates cache-striding patterns that can reduce throughput by 10× on large matrices.
  • Forgetting to specify inner dimension: void f(int arr[][]) is invalid — inner dimensions must be compile-time constants for C-style 2D array parameters.
  • Out-of-bounds on flat indexing: In flat vector indexing, arr[row * cols + col] — swapping rows and cols produces out-of-bounds access for non-square matrices.

Best Practices

  • Always iterate in row-major order (outer loop over rows, inner over columns) for cache efficiency.
  • For runtime-sized matrices, prefer a flat std::vector<T> with m[row * cols + col] indexing over vector-of-vectors for better cache performance.
  • Consider wrapping a flat 2D matrix in a class that overloads operator()(row, col) for clean, expressive syntax without exposing raw indexing arithmetic.