How would you design 2D data structures for grids, matrices, or sparse maps?
Designing and building 2D data structures (grids, matrices, sparse maps) involves choosing storage (dense array-of-arrays vs flat typed array vs sparse Map keyed by 'r,c'), defining mutation API, and reasoning about access patterns. Trade-off: dense storage is cache-friendly and indexable but wastes memory if sparse; sparse Maps save memory for empty cells but lose locality. Pick based on density and access pattern (random vs sequential, row-major vs column-major).
What's being asked
This is an open-ended design prompt: build a 2D data structure. Interviewer is looking for you to ask clarifying questions, pick a representation with reasoning, implement core ops, and discuss trade-offs.
Clarify first
- Dimensions: fixed (10x10 board) or growable (infinite plane)?
- Density: mostly full (image bitmap) or mostly empty (sparse drawing)?
- Access pattern: random get/set, row scans, neighbor lookup?
- Mutation: cells change, rows/cols insert/delete, or static after build?
- Concurrency: single-threaded or multi-reader?
Option 1 — Dense, array-of-arrays
class Grid2D {
constructor(rows, cols, fill = 0) {
this.rows = rows;
this.cols = cols;
this.data = Array.from({ length: rows }, () => new Array(cols).fill(fill));
}
get(r, c) { return this.data[r]?.[c]; }
set(r, c, v) { this.data[r][c] = v; }
forEach(fn) {
for (let r = 0; r < this.rows; r++)
for (let c = 0; c < this.cols; c++) fn(this.data[r][c], r, c);
}
}Simple, idiomatic. Sub-arrays have pointer overhead — bad cache locality.
Option 2 — Flat typed array (cache-friendly)
class Grid2DFlat {
constructor(rows, cols) {
this.rows = rows;
this.cols = cols;
this.data = new Float64Array(rows * cols);
}
idx(r, c) { return r * this.cols + c; }
get(r, c) { return this.data[this.idx(r, c)]; }
set(r, c, v) { this.data[this.idx(r, c)] = v; }
}Contiguous memory, fastest for numeric workloads (image processing, simulation). Resizing is O(n).
Option 3 — Sparse Map
class Sparse2D {
constructor() { this.cells = new Map(); }
key(r, c) { return `${r},${c}`; }
get(r, c) { return this.cells.get(this.key(r, c)); }
set(r, c, v) { this.cells.set(this.key(r, c), v); }
delete(r, c) { this.cells.delete(this.key(r, c)); }
}O(1) get/set, memory ∝ non-empty cells. Loses row-scan locality. Stringifying keys is slower than indexing.
Option 4 — Map of Maps (sparse, row-grouped)
class SparseRows2D {
constructor() { this.rows = new Map(); }
set(r, c, v) {
if (!this.rows.has(r)) this.rows.set(r, new Map());
this.rows.get(r).set(c, v);
}
get(r, c) { return this.rows.get(r)?.get(c); }
rowScan(r, fn) { this.rows.get(r)?.forEach((v, c) => fn(v, c)); }
}Sparse + row scan is fast.
Common operations to implement
neighbors(r, c) {
const out = [];
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]])
if (this.get(r+dr, c+dc) !== undefined) out.push([r+dr, c+dc]);
return out;
}
transpose() {
const t = new Grid2D(this.cols, this.rows);
this.forEach((v, r, c) => t.set(c, r, v));
return t;
}
rotate90() { /* ... */ }Trade-off matrix
| Use case | Best representation |
|---|---|
| Game board, fixed size | Array-of-arrays |
| Image / numeric matrix | Flat typed array |
| Sparse infinite canvas | Map of 'r,c' |
| Sparse with row queries | Map of row Maps |
| Spreadsheet (sparse, columnar reads) | Two Maps (row + col index) |
What an interviewer wants to hear
- You asked about density and access pattern before coding.
- You named the trade-off (locality vs memory vs flexibility).
- You picked a representation and justified it.
- You handled out-of-bounds and empty cells deliberately.
- You can sketch a second representation if requirements change.
Mental model
A 2D structure is just a function (row, col) → value. The representation is purely an indexing/storage choice. Density and access pattern drive the choice; everything else is API ergonomics.
Follow-up questions
- •How would you make it growable in both dimensions?
- •How would you serialize it for transport?
- •How would you support undo/redo?
- •How does the choice change if reads are 100x more common than writes?
Common mistakes
- •Jumping to code before asking about density and dimensions.
- •Using Array(rows).fill(Array(cols)) — all rows share the same inner array.
- •Stringifying keys ('r,c') without realizing it costs ~50ns vs flat index ~2ns.
- •Forgetting bounds checks — silent undefined reads.
- •Ignoring locality for hot row-scan workloads.
Performance considerations
- •Flat typed arrays are 5-10x faster than nested arrays for numeric workloads due to cache locality and lack of pointer chasing. Sparse Maps with string keys allocate per write — avoid in hot loops. For 1000x1000+ grids the representation choice dominates everything else.
Edge cases
- •Negative coordinates (infinite plane).
- •Resizing while iterating.
- •Floating-point keys — not allowed; coerce to int.
- •Very sparse with very high coordinates — Map wins decisively.
Real-world examples
- •Canvas ImageData uses a flat Uint8ClampedArray.
- •Excel/Sheets internally use sparse representations.
- •Game-of-life simulators use flat typed arrays for speed.
- •Figma's infinite canvas uses a spatial index, not a dense grid.