A dynamic array's size falls from a million to twelve — why doesn't its memory footprint fall too?
answer
- two numbers, not one
- which number does an erase change?
- the block is a single allocation
- capacity is a high-water mark
- giving it back means another copy
basics
~20 sA dynamic array tracks two separate numbers: size, the elements in use, and capacity, the slots allocated. Removing elements lowers size only. The underlying buffer stays as large as it ever grew until something explicitly shrinks it.
solid answer
~50 sA dynamic array is a fixed block of storage plus a `size` counter. `capacity` is how many slots the block holds; `size` is how many are logically in use. Erasing elements decrements `size` and leaves `capacity` alone, so capacity behaves as a high-water mark: it records the largest the structure ever got, not how big it is now. Nothing about erasing frees a byte — the block is a single allocation, and you cannot return the tail of it piecemeal. Handing the memory back means allocating a smaller block, copying the surviving elements into it, and releasing the old one, which is an O(n) operation someone has to ask for. In implementations that store handles rather than values inline, the slots past the logical size can also keep removed items alive until they are overwritten.
go deeper
Be ready to state the two numbers by name and say which one an erase changes. If you can say 'size went to twelve, capacity stayed at a million, and the block is one allocation', you have answered the screening version.
Explain why partial return is impossible: the storage is a single contiguous allocation, so reclaiming means a new smaller block plus a copy. Mention that abandoned slots can keep removed items alive if they are not overwritten.
Show that you would measure before acting — retained bytes per instance times instance count, over how long. Be ready to say that reclaiming costs an O(n) copy, briefly raises peak memory, and invalidates anything holding a position into the old storage.
Own the policy question: whether long-lived structures in your services should ever return their peak footprint, what that discipline costs in code and review attention, and whether a scheduled rebuild at a quiet moment beats per-operation cleverness.
## Two numbers, not one A dynamic (growable) array is built on a fixed-size block of contiguous storage. Because that block cannot be extended in place, the structure keeps two independent quantities: - **size** — how many elements are logically present. This is what iteration length, bounds checks and the "is it empty" test use. - **capacity** — how many element slots the currently allocated block can hold. This is a property of the *allocation*, not of the data. The invariant is `0 <= size <= capacity`. Everything surprising about memory in a growable array follows from the fact that these two numbers move independently: appends push `size` up and only occasionally push `capacity` up; erases push `size` down and, under the most common policies, never push `capacity` down at all. ## Why erasing frees nothing The block is one allocation. When your work queue drains from 1,048,576 entries to 12, the structure sets `size = 12` and possibly clears the abandoned slots — but the allocation is still one object of one size, and there is no way to return "the last 1,048,564 slots" of it to the allocator. Allocators hand out and take back whole blocks. So `capacity` is a **high-water mark**. It remembers the largest the structure ever became, for as long as the structure lives. That is a deliberate design choice, not an oversight: it makes the erase path cheap and predictable (no allocation, no copy, no invalidation), and it means a container that repeatedly fills and drains does its allocation work once instead of on every cycle. ## What it costs you Two distinct costs hide behind a retained capacity: 1. **Retained bytes.** A long-lived structure that once held a million entries holds the footprint of a million entries forever. Multiply by the number of such structures and the number of running instances and the number is often real. 2. **Retained *elements*.** If the storage holds handles/references rather than the values inline, the slots beyond `size` may still contain the old references. Logically the elements are gone; physically something still points at them, so they cannot be reclaimed. Careful implementations null out or destroy the abandoned slots on erase precisely to avoid this; naive hand-rolled ones do not. This is why "my structure is empty but memory did not drop" sometimes has *two* separate causes at once. ## Giving the memory back There is exactly one mechanism: allocate a smaller block, copy the live elements into it, release the old block. That is O(n) time, and while both blocks are live it *temporarily raises* peak memory rather than lowering it. It also moves every element, so any reference or position captured into the old block becomes meaningless. In other words, shrinking has the same cost profile and the same invalidation consequences as growing. That is why it is generally an explicit request rather than something that happens on every erase. | operation | changes size | changes capacity | moves elements | |---|---|---|---| | append within capacity | yes | no | no | | append past capacity | yes | yes (up) | yes | | erase | yes | no | shifts, if erasing mid-array | | clear | yes (to 0) | no | no | | explicit shrink | no | yes (down) | yes | ## Degrees of freedom across ecosystems The policy is genuinely a choice, and mainstream runtimes chose differently. Growable arrays in C++ and Rust never hand a byte back on their own — reducing the buffer is an explicit, and in one case non-binding, request. The list type in mainstream Python builds does the opposite and reallocates downward once the size falls well below the allocated slots. Managed runtimes such as those behind Java and C# sit with the first group: the backing block persists at its high-water mark until you ask for a trimmed copy. If you carry an assumption about which behaviour is "normal" from one ecosystem to another, you will be wrong half the time — which is exactly why interviewers ask this as a concept question rather than an API question. ## What to say in the room Name the two numbers, say that erase touches only one of them, say that the block is a single allocation so partial return is impossible, and say that reclaiming means a fresh smaller allocation plus a copy plus invalidation. That is the whole answer, and it generalises to every growable buffer you will ever meet, including string builders and byte buffers.
- Does clearing every element release the memory?No. Clear sets size to zero and leaves capacity untouched — the block is exactly as large as before. Worse, in storage that holds handles rather than inline values, the abandoned slots can keep the removed items alive unless the implementation overwrites them. Clearing is a cheap logical reset, not a memory operation.
- If capacity never shrinks, is memory use unbounded over the process lifetime?No — it is bounded by the peak size the structure ever reached, not by the total number of elements ever inserted. A container that cycles between 10 and 100 entries settles near a capacity for 100. The pathological case is a long-lived container that sees one rare spike and then idles at that footprint for months.
- How do you actually give the memory back?Allocate a smaller block, copy the survivors, release the old one — either through an explicit shrink operation where one exists, or by building a fresh structure sized to the survivors and dropping the old. Both are O(n), both briefly hold two blocks at once, and both move every element, so anything holding a position into the old storage is invalidated.
A rented warehouse: you can empty every shelf in an afternoon, but you keep paying for the same floor space until you sign a smaller lease and physically move the remaining stock.
saying these in an interview costs you the question
- Removing elements immediately frees the memory
- Size and capacity are the same number
- Shrinking the buffer is free because it only reduces memory
- Clearing the container releases every element it held
- Capacity always equals the current element count