Why does a growable array track both a size and a capacity, and what happens when they are equal?
answer
- two counters, not one
- one counts stored items
- the other counts available slots
- the interesting append is the boundary one
- allocate bigger, copy, release old
basics
~20 sSize is how many elements are stored; capacity is how many slots the underlying block can hold. Appending when size equals capacity forces allocating a larger block, copying every stored element into it, and releasing the old one.
solid answer
~40 sA growable array is built on a fixed-length block of memory, so it keeps two counters: `size`, the number of elements the caller has put in, and `capacity`, the number of slots the current block physically has. The gap between them is deliberate slack. While `size < capacity`, an append is a write at index `size` plus an increment — constant time, no allocation, no copying. When `size == capacity` there is no free slot, so the structure allocates a bigger block, copies all `size` elements across, releases the old block, and only then performs the write. That copying append costs O(n). The whole design bet is that over-allocating slack makes the copying append rare enough that appends are constant on average over a long run.
go deeper
Be ready to state the two counters and the invariant size <= capacity, and to describe the two append paths: a plain write when there is slack, and allocate-copy-release when there is not.
Explain why the slack exists at all — that growing by exactly one slot each time would copy the whole prefix on every append — and quantify the boundary append as O(n) in the current size.
Show you know where the boundary append actually hurts in production: a rare multi-millisecond call inside a hot ingest path, and the fact that the block's address changes when it grows.
Own the framing that capacity is a memory-versus-copying knob: buying more slack trades resident memory for fewer copies, and the right amount is a property of the workload, not a universal default.
## Two numbers because there are two different questions A growable array gives you the feel of a sequence that expands forever, but it is built on something that cannot expand: one contiguous block of memory with a fixed number of element slots, allocated once. Contiguity is the whole point — it is what makes indexing a single address computation, and what makes scanning the elements cache-friendly. Nothing about a contiguous block lets you extend it in place, because the memory immediately after it usually belongs to something else. So the structure keeps two counters: - **size** (also called length or count) — how many elements the caller has actually stored. This is what iteration, index bounds checks and "how many items do I have" all use. - **capacity** — how many element slots the currently allocated block contains. This is an implementation fact about memory, not about your data. The invariant is `0 <= size <= capacity`. The slots from `size` up to `capacity - 1` exist but hold nothing meaningful; they are pre-purchased room. ## The fast path and the slow path Appending has two behaviours, and knowing which one you are on is the entire subject: **Fast path (`size < capacity`).** Write the value into slot `size`, increment `size`. That is a couple of instructions: O(1) with a small constant, no allocation, no copying, no interaction with the memory allocator at all. The overwhelming majority of appends take this path. **Slow path (`size == capacity`).** There is no free slot, so the array must: 1. compute a new, larger capacity from its growth rule; 2. ask the allocator for a block of that size; 3. copy all `size` existing elements from the old block to the new one; 4. release the old block; 5. point itself at the new block and update `capacity`; 6. finally do the ordinary write. Step 3 touches every element already stored, so this append costs O(n) in the current size — and the bigger the array has grown, the more expensive that one append is. ## Why over-allocate at all? The alternative is to keep `capacity == size` always: grow by exactly one slot on every append. That is correct and maximally memory-frugal, and it is catastrophic — *every* append then reallocates and copies the whole prefix, so building an array of n elements copies roughly n²/2 elements in total. Slack is what buys the fast path. The growth rule decides how much slack you buy each time, and that choice is a real engineering tradeoff between wasted memory and copying work. ## Things capacity is not - **Capacity is not a limit you set on your data.** Exceeding it is not an error; it is a routine event that triggers a reallocation. It is not a bounded-queue capacity or a quota. - **Capacity is not visible in the data.** Iterating, printing or serializing a growable array shows `size` elements. The unused slack is invisible except in memory usage. - **Capacity does not shrink on its own** in most designs — that is a separate policy question, not part of append. - **Capacity is not the same as bytes used.** A block of `capacity` slots occupies `capacity × element-size` bytes, plus whatever bookkeeping the allocator adds. When elements are references to other objects, the block holds the references, not the objects. ## The boundary is where the interesting behaviour lives Everything memorable about growable arrays happens on the transition `size == capacity`: | Situation | Cost of this one append | Allocator involved? | |---|---|---| | `size < capacity` | O(1) | no | | `size == capacity`, n elements stored | O(n) copy plus allocation | yes | That is why the standard claim is that appending is *amortized* constant rather than simply constant: an individual append is either trivially cheap or proportional to everything you have stored so far, and the constant-time claim is about the run as a whole rather than about any one call. ## What this buys you day to day Because the block stays contiguous, index access is O(1) and iteration is fast regardless of how many reallocations happened along the way. The cost is paid in three places: the occasional expensive append, the memory sitting idle as slack, and the fact that the block's address changes whenever it grows — which matters to anything holding on to a position inside it. Different mainstream standard libraries make visibly different calls on how much slack to buy, which tells you there is no single right answer, only a workload you are tuning for.
- What exactly does an append do when it does not trigger a reallocation?It writes the value into the slot at index `size` in the block that already exists, then increments `size`. No allocation, no copying, no touching of the other elements — a couple of instructions, constant time regardless of how many elements are already stored.
- A growable array reports size 16 and capacity 16. What does the very next append cost?It copies all 16 existing elements into a freshly allocated, larger block, releases the old block, and then writes the 17th value. So that single call does 16 element copies plus an allocation, versus roughly zero work for the append before it.
- Why can't the structure just extend the existing block instead of copying?The block is contiguous, and the memory directly after it is generally already owned by something else, so there is nowhere to extend into. Some allocators can occasionally grow a block in place when the following region happens to be free, but a data structure cannot depend on that, so the general algorithm must assume allocate-and-copy.
A restaurant books a table for eight but has five diners seated: five is the size, eight is the capacity. Seating a sixth is instant; seating a ninth means moving the whole party to a bigger table.
saying these in an interview costs you the question
- Uses size and capacity as if they were the same number
- Says every append allocates a new block
- Claims the existing block is simply extended in place
- Cannot say what happens on the append that finds the block full
- Thinks the unused slots hold visible elements