For a spreadsheet-like grid, when does one flat buffer beat an array of separate row arrays?
answer
- what does this grid do most often
- one allocation versus many
- cost of moving a whole row
- a handle swap versus copying cols values
- a permutation array buys reordering for a lookup
basics
~20 sOne flat buffer wins when whole-grid passes dominate: a single allocation, contiguous scans, no per-access indirection. Separate row arrays win when the structure changes at row granularity — reordering, inserting or sharing rows costs a handle move instead of copying every cell.
solid answer
~60 sAsk what the grid does most. A flat buffer of `rows * cols` slots is one allocation, one stride, and a full pass is a single linear sweep; every access is a multiply-add with no second lookup, and the whole grid is one object to hand around. Its weakness is structural change: swapping two rows copies `cols` values, inserting a row shifts every value after it and may force a reallocation of the entire grid, and rows cannot vary in length or be shared. An array of row handles inverts every one of those. Swapping or reordering rows is a handle move, inserting a row shifts only `rows` handles, a row can be aliased by another view, and rows may differ in length. It pays for that with an extra indirection per access, one allocation per row, and rows that may be scattered so a whole-grid pass is no longer one sweep. A spreadsheet that mostly recalculates is the first case; one that mostly sorts, inserts and drags rows is the second — and the hybrid, a flat buffer plus a permutation array of row indices, buys cheap logical reordering for one extra lookup per access.
go deeper
Know the two shapes: one contiguous block addressed by arithmetic, or an array of separate rows reached through a handle. Be able to say that the first is a single allocation and the second is one per row.
Explain the concrete cost differences: a row swap is a handle move in nested storage and a copy of every column value in a flat buffer, while an access in nested storage costs an extra lookup and a full pass is no longer a single sweep.
Drive the decision from the workload. Identify whether the hot path is whole-grid recalculation or row-granularity editing, quantify the sort and insert costs both ways, and know the flat-plus-permutation hybrid and what it gives up.
Own the choice against team and fleet constraints: the per-allocation overhead multiplied by the row count on a memory ceiling, the discipline the flat form demands to avoid silent addressing bugs, and whether a grid that grows sideways should be a dense grid at all.
## Two ways to be a grid **Flat**: allocate one block of `rows * cols` slots and define the cell at `(r, c)` to live at `r * stride + c`. There is one object, one allocation, one addressing rule. **Nested**: allocate an array of `rows` handles, each pointing at its own row of `cols` slots. There are `rows + 1` objects and access is a lookup followed by a lookup. They model the same abstract grid and differ in what they make cheap. ## What the flat buffer buys - **One allocation.** Construction and release are single operations rather than `rows + 1` of them. For a grid rebuilt often, that alone can dominate. - **A full pass is one sweep.** Every cell of the grid is contiguous with the next, so a row-order traversal walks memory linearly from the first slot to the last — the ideal access pattern, and one that stays ideal across row boundaries. - **No indirection.** An access is an index computation and one read. The nested form must read the row handle first, and that read can itself be the expensive part when the handle array is large. - **Predictable footprint.** `rows * cols` slots plus a fixed header, with no per-row bookkeeping and no per-allocation overhead multiplied by the row count. On a memory-constrained fleet this is a real number, not a rounding error. - **Trivially copyable and transferable.** One contiguous block can be snapshotted, checksummed, or written out as a unit. ## What the nested form buys - **Row-granularity structure is nearly free.** Swapping two rows swaps two handles: `O(1)` regardless of the column count. In the flat form the same swap copies `cols` values. Sorting the grid by a column is `O(rows log rows)` handle moves versus `O(rows log rows * cols)` value copies. - **Insertion and deletion of rows are cheap.** Inserting a row shifts `rows` handles rather than `rows * cols` values, and does not require the whole grid to be reallocated as one block. - **Rows can be shared or aliased.** A view, an undo snapshot, or a frozen header row can reference the same row storage without copying it. A flat buffer has no sub-object to reference. - **Rows may differ in length.** The representation simply does not constrain them, which is a feature when the data is genuinely ragged and a hazard otherwise. - **Growth is incremental.** Adding a row allocates one row. Growing a flat grid by a row may mean allocating a whole new block and copying every existing cell. ## Reading the workload The decision is not about which structure is faster; it is about which operation is on the hot path. - **Recalculation-dominated** — full passes over every cell, formula evaluation, rendering the visible region, aggregate computation. Flat. The pass is the workload and the pass is a sweep. - **Edit-dominated at row granularity** — sorting by a column, dragging rows, inserting and deleting, filtering into views, undo stacks that snapshot rows. Nested. Structure changes cost handles, not cells. - **Both** — which is the honest description of a real spreadsheet. That is what the hybrids are for. ## The hybrids worth knowing **Flat buffer plus a row permutation.** Keep all values in one block in their original physical order, and maintain a separate array mapping logical row index to physical row index. Reordering rows becomes a permutation edit — `O(1)` per swap, `O(rows)` for an arbitrary reorder — while memory stays a single allocation. The cost is one extra lookup per access and the loss of the pure linear sweep: a logical-order full pass now visits physical rows out of order, though each row is still internally contiguous, so the penalty is far smaller than a column-strided walk. Physically compacting the grid to match the permutation, when the edit rate quiets down, restores the sweep. **Flat values plus a row-offset array.** Rows stay contiguous and adjacent in one buffer, with an offsets array recording where each begins. This keeps one allocation and permits variable row lengths, at the price of expensive single-row growth: lengthening one row shifts all the slots after it. ## What actually decides it in a team Two constraints usually settle the argument before performance does. **Column growth is expensive in both, and worse in flat.** Adding a column to a flat grid changes the stride, which means relaying out every row — a full copy. Adding one to a nested grid means growing every row individually, `rows` separate operations. Neither is cheap, so a grid that grows sideways often deserves a different structure entirely. **Maintainability.** The flat form pushes index arithmetic into the code and rewards discipline: one addressing helper, a stride stored explicitly, invariants checked at construction. A team that will not hold that discipline is safer with the nested form, whose worst failure is slowness rather than corruption. Choosing the faster representation and then paying for a class of silent addressing bugs across a codebase is a bad trade unless the sweep really is the product. The answer an interviewer wants is not a winner. It is: name the dominant operation, state what each layout makes cheap, and pick the hybrid only when the workload genuinely has two hot paths.
- Sorting the grid by one column is the hot path. Quantify the difference between the two layouts.The comparison count is the same, `O(rows log rows)`; the movement cost is not. Nested storage moves a handle per swap, so the sort is `O(rows log rows)` moves. A flat buffer moves a whole row per swap, so it is `O(rows log rows * cols)` value copies — a factor of the column count. That factor is exactly why a flat grid on a sort-heavy path usually gains a row permutation array instead of physically reordering.
- You choose the flat buffer plus a row permutation. What do you give up?One extra lookup on every cell access, and the pure linear sweep: a pass in logical row order now visits physical rows out of sequence, though each row remains internally contiguous so the penalty is modest. You also carry a second array to keep consistent with the buffer, which is a real correctness surface. Periodically compacting the grid to match the permutation restores the sweep when the edit rate drops.
- How does adding a column compare between the two layouts?Both are expensive, which is the point. In a flat buffer the stride changes, so every row must be relaid out — a full copy of the grid. In nested storage each of the `rows` row arrays must grow individually, which is `rows` separate operations and likely `rows` reallocations. A grid that grows sideways frequently is signalling that neither dense layout fits its access pattern.
saying these in an interview costs you the question
- Says the flat buffer is simply faster, without naming the workload
- Thinks nested rows remove the cost of column-wise traversal
- Ignores that a flat row swap copies every value in the row
- Assumes rows in a nested grid sit next to each other in memory
- Forgets the extra lookup and per-row overhead of nested storage
- Treats adding a column as cheap in the flat layout